### 问题描述 小然是一个魔方爱好者，他特别喜欢挑战各种不同的魔方。他现在面临的问题是一个特殊的魔方——平衡魔方。这个魔方的每个面都有一个值，形成一个长度为 $N$ 的数组 $A_i$。 小然发现，任何一个面的值都可以分裂成两个正数 $X$ 和 $Y$，满足 $X + Y = A_i$。每次分裂操作后，魔方的面数会增加 $1$。 小然希望通过一系列操作，使得魔方的所有面的值的奇偶性都相同。你能帮助他找出实现这个目标所需的最小操作次数吗？ ### 输入格式 输入的第一行包含一个整数 $T$，表示测试用例的数量。 每个测试用例包含两行。第一行是一个整数 $N$，表示魔方上的面的数量。第二行是 $N$ 个空格分隔的整数 $A_1, A_2, ..., A_N$，表示魔方每一面的值。 ### 输出格式 对于每个测试用例，输出一个整数，表示为了使所有面的值的奇偶性相同所需的最小操作次数。 ### 样例输入 ```text 2 4 1 3 5 7 3 1 2 3 ``` ### 样例输出 ```text 0 1 ``` ### 说明 在第一个测试用例中，所有面的值都是奇数，所以不需要进行任何操作。 在第二个测试用例中，我们可以选择值为 $2$ 的面进行分裂，得到两个值为 $1$ 的面，此时所有面的值都是奇数，所以只需要一次操作。 ### 评测数据范围 $1 \leq T \leq 1000$。 $1 \leq N \leq 10^5$。 $1 \leq A_i \leq 10^9$。 所有测试用例的 $N$ 之和不超过 $2 \times 10^5$。