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