有一个书架,可容纳 $$$n$$$ 本书。如果书架上的第 $$$i$$$ 位置有书,则 $$$a_i = 1$$$,否则 $$$a_i = 0$$$。保证书架上至少有一本书。
在一次移动中,您可以选择一些连续的段 $$$[l; r]$$$ 由书籍组成(即,对于从 $$$l$$$ 到 $$$r$$$ 的每个 $$$i$$$,条件 $$$a_i = 1$$$ 成立)并且:
- 将其向右移动 $$$1$$$:将所有 $$$l \le i \le r$$$ 的索引 $$$i$$$ 处的书移动到 $$$i + 1$$$。仅当 $$$r+1 \le n$$$ 并且位置 $$$r+1$$$ 处没有书时才可以进行此移动。
- 将其向左移动 $$$1$$$:将所有 $$$l \le i \le r$$$ 的索引 $$$i$$$ 处的书移动到 $$$i-1$$$。仅当 $$$l-1 \ge 1$$$ 并且位置 $$$l-1$$$ 处没有书时才可以进行此移动。
您的任务是找到将书架上的所有书籍收集为连续(连续)段(即没有任何间隙的段)所需的最少移动次数。
例如,对于 $$$a = [0, 0, 1, 0, 1]$$$ 书籍之间有间隙(当 $$$a_3 = 1$$$ 且 $$$a_5 = 1$$$ 时,$$$a_4 = 0$$$),对于 $$$a = [1, 1, 0]$$$ 书籍之间没有间隙,对于 $$$a = [0, 0,0]$$$ 书之间也没有间隙。
您必须回答 $$$t$$$ 独立测试用例。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 200$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — 书架上的位置数。测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 1$$$),其中如果该位置有一本书,则 $$$a_i$$$ 为 $$$1$$$,否则为 $$$0$$$。保证书架上至少有一本书。
输出
对于每个测试用例,打印一个整数:将书架上的所有书籍收集为连续(连续)段(即没有间隙的段)所需的最小移动次数。
示例
输入 #1
5 7 0 0 1 0 1 0 1 3 1 0 0 5 1 1 0 0 1 6 1 0 0 0 0 1 5 1 1 0 1 1
输出 #1
2 0 2 4 1
注意
在示例的第一个测试用例中,您可以移动段 $$$[3; 3]$$$ 向右,段 $$$[4; 5]$$$ 向右。在所有移动之后,书籍形成连续段 $$$[5; 7]$$$。所以答案是$$$2$$$。
在示例的第二个测试用例中,您无需执行任何操作,书架上的所有书籍都已形成连续的段。
在示例的第三个测试用例中,您可以移动段 $$$[5; 5]$$$ 向左,然后是段 $$$[4; 4]$$$ 再次向左。在所有移动之后,书籍形成连续段 $$$[1; 3]$$$。所以答案是$$$2$$$。
在示例的第四个测试用例中,您可以移动段$$$[1; 1]$$$ 向右,段$$$[2; 2]$$$ 向右,段 $$$[6; 6]$$$ 向左,然后是段 $$$[5; 5]$$$ 向左。在所有移动之后,书籍形成连续段 $$$[3; 4]$$$。所以答案是$$$4$$$。
在示例的第五个测试用例中,您可以移动段 $$$[1; 2]$$$ 向右。在所有移动之后,书籍形成连续段 $$$[2; 5]$$$。所以答案是$$$1$$$。