给定一个包含 $$$n$$$ 正整数的数组 $$$a$$$。
在一次操作中,您可以选择任意一对索引 $$$(i, j)$$$,使得 $$$a_i$$$ 和 $$$a_j$$$ 具有不同的奇偶性,然后用它们的总和替换较小的索引。更正式地说:
- 如果 $$$a_i < a_j$$$,则将 $$$a_i$$$ 替换为 $$$a_i + a_j$$$;
- 否则,将 $$$a_j$$$ 替换为 $$$a_i + a_j$$$。
求使数组的所有元素具有相同奇偶校验所需的最少操作数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 所需的最少操作数。
示例
输入 #1
7 5 1 3 5 7 9 4 4 4 4 4 3 2 3 4 4 3 2 2 8 6 4 3 6 1 2 1 6 3 6 1 2 1 2 5 999999996 999999997 999999998 999999999 1000000000
输出 #1
0 0 2 4 3 3 3
注意
在第一个测试用例中,所有整数已经具有相同的奇偶校验。因此,不需要进行任何操作。
在第三个测试用例中,我们可以执行两个操作 $$$(1, 2)$$$ 和 $$$(1, 3)$$$。数组 $$$a$$$ 变换如下: $$$a = [\color{red}2, \color{red}3, 4] \longrightarrow [\color{red}5, 3, \color{red}4] \longrightarrow [5, 3, 9]$$$。
在第四个测试用例中,最佳操作序列的示例是 $$$(1, 2)$$$、$$$(1, 3)$$$、$$$(1, 4)$$$ 和 $$$(1, 4)$$$。数组 $$$a$$$ 变换如下: $$$a = [\color{red}3, \color{red}2, 2, 8] \longrightarrow [\color{red}3, 5, \color{red}2, 8] \longrightarrow [\color{red}3, 5, 5, \color{red}8] \longrightarrow [\color{red}{11}, 5, 5, \color{red}8] \longrightarrow [11, 5, 5, 19]$$$。