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 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