Students have started queuing up to look at their minor copies. The professor was standing right behind all of them and caught them making fun of him. Professor went furious and planned on dividing the queue as follows:

1. Let's assume that students are numbered as a sequence from 1 to n, and for $1\leq i \leq N$, a_i points are scored by student i.
2. The professor wants to divide the sequence in multiple contiguous subsequences such that sum of each of them is a multiple of 2.

Since the professor got confused, he asks for your help to find the maximum number of such subsequences.

Input

The first line consists of a single integer T, denoting the number of test cases. The description of each test case follows:

The first line of each test case consists of a single integer N The second line consists of N space separated integers denoting a₁,a₂,....,a_N.

Output

For each test case, print a single integer denoting the maximum number of contiguous subsequences as described above. If the professor is unable to divide, print -1.

Constraints

$1\leq T \leq 10$
$1\leq N \leq 10^{6}$
$1\leq a_i \leq 10^{9}$