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