Given an array of $N$ integers

You have to transform the array, for every $i (1 \leq i \leq N)$: $a[i] = a[i] \%2$

For example: if the given array is 3,4,5 then after the transformation the array will be 1,0,1

Your task is to convert the array into a palindrome and for that you can re-arrange the elements however you wish

Is it possible to convert the array into a palindrome?

Input :
The first line contains $T$, the number of test cases $1 \leq T \leq 10^3$
The second line contains $N$, the number of array elements $1 \leq N \leq 10^5$
The third line contains $N$ integers, the array elements $1 \leq a[i] \leq 10^9$

Output:
For all test cases print $1$ if the array can be converted into a palindrome or else print $0$