给定一个序列 $$$a_1, a_2, \ldots, a_n$$$,找到要从序列中删除的元素的最小数量,使得删除后,每个 $$$2$$$ 连续元素的总和为偶数。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2,\dots,a_n$$$ ($$$1\leq a_i\leq10^9$$$) — 序列的元素。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,打印一个整数 - 要从序列中删除的最小元素数,以使每个 $$$2$$$ 连续元素的总和为偶数。
示例
输入 #1
2 5 2 4 3 6 8 6 3 5 9 7 1 3
输出 #1
1 0
注意
在第一个测试用例中,删除$$$3$$$后,序列变为$$$[2,4,6,8]$$$。连续元素对是 $$$\{[2, 4], [4, 6], [6, 8]\}$$$。现在每个连续对的总和都是偶数。因此,我们只需要删除 $$$1$$$ 元素即可满足所要求的条件。
在第二个测试用例中,每个连续对已经有偶数和,因此我们不需要删除任何元素。