有一个功能区,分为 $$$n$$$ 个单元格,从左到右编号为 $$$1$$$ 到 $$$n$$$。每个单元要么包含一个芯片,要么是免费的。
您可以执行以下操作任意次数(可能为零):选择一个筹码并将其移动到左侧最近的空闲单元。您可以选择任何您想要的芯片,只要其左侧至少有一个空闲单元即可。当您移动芯片时,操作前所在的单元格就会空闲。
您的目标是移动芯片,使它们形成一个块,并且它们之间没有任何空闲单元。您必须执行的最少操作次数是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例由两行组成:
- 第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 50$$$) — 单元格数量;
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$); $$$a_i = 0$$$ 表示第 $$$i$$$ 个单元格空闲; $$$a_i = 1$$$ 表示第 $$$i$$$ 个单元包含一个芯片。
对输入的附加约束:在每个测试用例中,至少一个单元包含芯片。
输出
对于每个测试用例,打印一个整数 - 您必须执行的最小操作数,以便所有芯片形成一个块,并且它们之间没有任何空闲单元。
示例
输入 #1
5 8 0 1 1 1 0 1 1 0 6 0 1 0 0 0 0 6 1 1 1 1 1 1 5 1 0 1 0 1 9 0 1 1 0 0 0 1 1 0
输出 #1
1 0 0 2 3
注意
在第一个示例中,您可以对第 $$$7$$$ 单元格中的芯片执行操作。左边最近的空闲单元格是第 $$$5$$$ 个单元格,因此它会移动到那里。之后,所有芯片形成一个块。
在第二个示例中,所有芯片都已位于单个块中。第三个例子也一样。