You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你和你的朋友正在玩游戏 Mortal Kombat XI。你们正在尝试通过一个挑战塔。这个塔里有 $n$ 个 Boss，编号从 $1$ 到 $n$。第 $i$ 个 Boss 的类型为 $a_i$。如果第 $i$ 个 Boss 是简单的，则 $a_i = 0$，否则这个 Boss 是困难的，$a_i = 1$。

在一次回合中，你或你的朋友可以击败一到两个 Boss（每一回合都必须击败至少一个 Boss，不能跳过）。每次都是你朋友先行动，然后轮到你，再轮到你朋友，如此交替。第一回合由你的朋友开始。

你的朋友需要提升技术，因为他实际上无法击败困难 Boss。为了击败困难 Boss，他需要使用跳过点。每使用一个跳过点可以击败一个困难 Boss。

你的任务是计算，为了让你和你的朋友按顺序击败所有 $n$ 个 Boss，你的朋友最少需要用多少个跳过点。

例如：假设 $n = 8$，$a = [1, 0, 1, 1, 0, 1, 1, 1]$。那么最优的做法如下：

• 你的朋友击败前两个 Boss，对第一个 Boss 使用一个跳过点；
• 你击败第三和第四个 Boss；
• 你的朋友击败第五个 Boss；
• 你击败第六和第七个 Boss；
• 你的朋友击败最后一个 Boss，并使用一个跳过点。这样总共用了两个跳过点完成了挑战塔。

你需要回答 $t$ 组独立的测试用例。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。接下来是 $t$ 组测试用例。

每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示 Boss 的数量。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 1$），其中 $a_i$ 表示第 $i$ 个 Boss 的类型。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$（$\sum n \le 2 \cdot 10^5$）。

输出格式

对于每组测试用例，输出一个整数，表示你朋友最少需要使用多少个跳过点，才能让你们按顺序击败所有 $n$ 个 Boss。

6
8
1 0 1 1 0 1 1 1
5
1 1 1 1 0
7
1 1 1 1 0 0 1
6
1 1 1 1 1 1
1
1
1
0

2
2
2
2
1
0