← 返回题目列表

Codeforces · 1777/A

A. 每个人都喜欢好的阵列!

中文机器翻译题面 查看原题

如果对于所有相邻元素对,$$$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$$$ 操作。