房间中共有 $n$ 盏灯，初始状态可以用 $a_1\dots a_n$ 表示，其中 $\tt 0$ 表示这盏灯初始是关闭的，$\tt 1$ 表示这盏灯初始是打开的。
从第一天早晨开始，魔王与勇士轮流行动：
- 每天早晨，魔王可以选择 **连续的** 两盏灯，将它们的状态全部设定为 $\tt 0$；
- 每天晚上，勇士可以选择 **任意的** 至多三盏灯，将它们的状态全部设定为 $\tt 1$。
每次行动时选择的灯在设定前的状态任意。
假设双方均采用最优策略，不会进行任何不利于自己的行动。勇士想知道，**最少** 需要多少天（也即，他最少需要多少次操作）才能将所有灯状态设定为 $\tt 1$——这样，他才能抓到可恶的魔王，迎娶美丽的公主。
## Input
第一行一个整数 $T$，表示数据组数。
对于每组数据：
+ 第一行一个整数 $n$，表示灯的总数。
+ 第二行共 $n$ 个数，依次表示 $a_1\dots a_n$。
## Output
对于每组数据，一行一个整数，代表勇士抓到魔王所需要的最少天数。
特别地，如果勇士不需要任何操作，输出 $0$ 即可。
[samples]
## Background
终于，勇士打败了魔王，他把走投无路的魔王困在了一个房间里。
魔王拥有在黑暗中随意穿行的能力，所以勇士只有把房间里所有的灯全部打开，才能找到魔王，最终彻底消灭他。
## Note
### 样例解释 1
+ 第一天早晨，魔王关闭第 $1{,}2$ 两盏灯；
+ 第一天晚上，勇士打开 $1{,}2{,}4$ 三盏灯。
### 样例解释 2
+ 第一天早晨，魔王关闭第 $4{,}5$ 两盏灯；
+ 第一天晚上，勇士打开 $2{,}3{,}4$ 三盏灯。
+ 第二天早晨，魔王关闭第 $1{,}2$ 两盏灯；
+ 第二天晚上，勇士打开 $1{,}2{,}5$ 三盏灯。
### 数据规模与约定
**本题采用捆绑测试**。
- Subtask 0（10 points）：$n \leq 10$，$T \leq 2046$。
- Subtask 1（30 points）：$ n \leq 2000$。
- Subtask 2（10 points）：初始所有灯都是关闭的。
- Subtask 3（20 points）：数据随机生成。
- Subtask 4（30 points）：无特殊限制。
对于所有数据，$1 \leq T \leq 10^6$，$1 \leq n \leq 10^6$，$1 \leq \sum n \leq 3 \times 10^6$。