You are given an array A of N integers. If you make the array whole using the following operation, then what is the minimum number of operations required to make the entire array even?

Note: It can be proved that this is always possible.

Operation

Select an index \(1 \leq i <N\) and perform operation:

P=A_i+A_i+1; Q=A_i-A_i+1;

A_i=P; A_i+1=Q;

Input format

The first line contains an integer T denoting the number of the test cases.
In each test case:
- The first line contains an integer N denoting the number of elements in the array.
- The second line contains N space-separated integers of array A.

Output format

For each test case print a single line denoting the minimum number of operations required to make the whole array even.

Constraints

\(1 \leq T \leq 20000\)
\(2 \leq N \leq 200000\)
\(1 \leq A_i \leq 1e9 \forall i \in [1,N]\)
Sum of N over all test cases will not exceed 200000