题目背景

终于，勇士打败了魔王，他把走投无路的魔王困在了一个房间里。

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

题目描述

房间中共有 $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$。