Chef has an array A of length N. In one operation, Chef can choose any element A_{i} and split it into two positive integers X and Y such that X+Y = A_{i}.
Note that the length of array increases by 1 after every operation.

Determine the minimum numbers of operations required by Chef to make [parity] of all the elements same.

It is guaranteed that parity of all the elements can be made equal after applying the above operation zero or more times.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of multiple lines of input.
• The first line of each test case contains a single integer N — the length of array A.
• Next line contains $N space-separated integers A_{1}, A_{2}, A_{3}, \dots, A_{N} -$ denoting the array A.

------ Output Format ------

For each test case, output the minimum number of operations required to make parity of all elements same.

------ Constraints ------

$1 ≤ T ≤ 4000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ does not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------
2
4
1 3 5 7
3
1 2 3

----- Sample Output 1 ------
0
1

----- explanation 1 ------
Test case $1$: All the elements have the same parity since all are odd. Thus, we need zero operations.

Test case $2$: In one operation, we can split the element $A_{2} = 2$ to $X = 1$ and $Y = 1$ such that $X+Y = 2$. Thus, the array now becomes $A = [1, 1, 1, 3]$. All the elements have the same parity since all are odd. Thus, we need only one operation.

见题面

见题面