「SFCOI-3」进行一个魔的除 I

终于，勇士打败了魔王，他把走投无路的魔王困在了一个房间里。 魔王拥有在黑暗中随意穿行的能力，所以勇士只有把房间里所有的灯全部打开，才能找到魔王，最终彻底消灭他。

房间中共有 $n$ 盏灯，初始状态可以用 $a_1\dots a_n$ 表示，其中 $\tt 0$ 表示这盏灯初始是关闭的，$\tt 1$ 表示这盏灯初始是打开的。 从第一天早晨开始，魔王与勇士轮流行动： - 每天早晨，魔王可以选择 **连续的** 两盏灯，将它们的状态全部设定为 $\tt 0$； - 每天晚上，勇士可以选择 **任意的** 至多三盏灯，将它们的状态全部设定为 $\tt 1$。 每次行动时选择的灯在设定前的状态任意。 假设双方均采用最优策略，不会进行任何不利于自己的行动。勇士想知道，**最少** 需要多少天（也即，他最少需要多少次操作）才能将所有灯状态设定为 $\tt 1$——这样，他才能抓到可恶的魔王，迎娶美丽的公主。

第一行一个整数 $T$，表示数据组数。 对于每组数据： + 第一行一个整数 $n$，表示灯的总数。 + 第二行共 $n$ 个数，依次表示 $a_1\dots a_n$。

对于每组数据，一行一个整数，代表勇士抓到魔王所需要的最少天数。 特别地，如果勇士不需要任何操作，输出 $0$ 即可。

4
5
1 0 1 0 1
5
1 0 0 1 1
9
0 0 0 0 0 0 0 0 0
13
0 1 0 0 1 0 1 0 0 0 0 0 0

1
2
5
8

### 样例解释 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$。