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