题目描述

小伦喜欢玩部落冲突——一款ios端手游，现在他计划利用炸弹人摧毁敌军的城墙，这样就用可以用巨人进攻敌军的大本营了。

当一块墙的血量低于等于0，则视为被摧毁。要使用巨人进攻敌军的大本营，小伦必须摧毁至少两块墙。


一个炸弹人可以对一块墙造成2点爆炸伤害，并使相邻的墙受到1点溅射伤害。


请问小伦至少需要多少的炸弹人才能摧毁城墙并用巨人进攻敌军的大本营。

输入格式

首先输入一个正整数t，表示共有t组数据 (110)

输入一行包含n+1个正整数，n和n个正整数a1,a2...an。

n表示城墙长度 (22e6)，ai表示每块墙的血量 (11e12)

输出格式

输出t行，每行一个正整数x，如题所示。

6
5 20 10 30 10 20
3 1 8 1
6 7 6 6 8 5 8
6 14 3 8 10 15 4
4 1 100 100 1
3 40 10 10

10
1
4
4
2
7

提示

一道不需要算法的水题。