← 返回题目列表

Codeforces · 1691/A

A. 克服困难

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

给定一个序列 $$$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$$$ 元素即可满足所要求的条件。

在第二个测试用例中,每个连续对已经有偶数和,因此我们不需要删除任何元素。