如果对于所有相邻元素对,$$$a_i$$$ 和 $$$a_{i+1}$$$ ($$$1\le i \lt n$$$) 具有不同的奇偶校验,则数组 $$$a$$$ 是好的。请注意,大小为 $$$1$$$ 的数组非常好。
给定一个大小为 $$$n$$$ 的数组。
在一次操作中,您可以选择任意一对相邻元素,其中两个元素具有相同的奇偶校验,将其删除,并将它们的乘积插入到相同位置。
找到形成一个好的数组的最少操作次数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^{9}$$$)。
输出
对于每个测试用例打印一个整数,形成一个好的数组所需的最少操作数。
示例
输入 #1
3 5 1 7 11 2 13 4 1 2 3 4 6 1 1 1 2 2 3
输出 #1
2 0 3
注意
考虑第一个测试用例。选择 $$$2$$$-nd 和 $$$3$$$-rd 整数并对它们应用运算。数组从 $$$[1, \color{red}{7}, \color{red}{11}, 2, 13]$$$ 更改为 $$$[1, \color{red}{77}, 2, 13]$$$。接下来,选择 $$$1$$$-st 和 $$$2$$$-nd 整数,数组从 $$$[\color{red}{1}, \color{red}{77}, 2, 13]$$$ 更改为 $$$[\color{red}{77}, 2, 13]$$$。因此我们需要 $$$2$$$ 操作。可以证明这是最少的运算次数。
在第二个测试用例中,给定的数组已经很好。所以我们需要 $$$0$$$ 操作。