题目描述

你和你的朋友正在玩《真人快打 XI》（Mortal Kombat XI）。你们正试图通过一个挑战塔。

在这个塔中有 $n$ 个 Boss，编号从 $1$ 到 $n$。第 $i$ 个 Boss 的类型为 $a_i$。如果第 $i$ 个 Boss 是简单的，那么它的类型为 $a_i=0$；否则，它是困难的，类型为 $a_i=1$。

在每一轮中，你或你的朋友可以击败一或两个 Boss（你和你的朋友都不能跳过回合，所以每一轮击败的 Boss 数量最少为 $1$）。在你的朋友的回合结束后，你的回合开始；然后又是你朋友的回合，接着是你的回合，依此类推。第一个回合是你朋友的回合。

你的朋友是个菜鸟，无法击败困难 Boss 。为了击败它们，他需要使用跳过点数。一个跳过点数可以用来击败一个困难 Boss。

你的任务是找到你的朋友需要使用的最少跳过点数，以便你和你的朋友按照给定的顺序击败所有 $n$ 个 Boss。

例如，假设 $n=8$， Boss 类型为 $a = [1, 0, 1, 1, 0, 1, 1, 1]$。那么最好的策略如下：

• 你的朋友击败前两个 Boss，为第一个 Boss 使用一个跳过点数。
• 你击败第三和第四个 Boss。
• 你的朋友击败第五个 Boss。
• 你击败第六和第七个 Boss。
• 你的朋友击败最后一个 Boss，使用一个跳过点数。

因此，完成挑战塔总共使用了 $2$ 个跳过点数。

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

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 2 \cdot 10^4$)，表示测试用例的数量。

对于每个测试用例： 第一行包含一个整数 $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 的类型。

输出格式

对于每个测试用例，输出一个整数，即你的朋友需要使用的最少跳过点数。

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

数据规模与约定

对于所有测试用例，保证 $\sum n \le 2 \cdot 10^5$。