Sort Odd-Even Ways

You are given an array ‘ARR’ of size ‘N’. The array contains ‘N’ positive integers.

You want to sort the array in ascending order by doing some operations.

In one operation, you can select two adjacent indexes and swap them if the parity of both values is not the same. In other words, you can only swap two elements if they are adjacent and one is odd, and the other is even.

Can you tell if you can sort the array?

Example :

N = 4
ARR =[ 1, 0, 3, 2 ]
If we swap ‘1’ and ‘0’ and ‘3’ and ‘2’, after applying these operations, our array becomes sorted. So ‘ANS’ is ‘1’.

Input Format :

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains an integer, ‘N’, denoting the size of the array ‘ARR’.

The second line of each test case contains ‘N’ integers denoting the elements of array ‘ARR’.

Output format :

For each test case, print '1' if you can sort 'ARR' using some number of operations else print '0'. Print the output of each test case in a new line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N  <= 10^4
0 <= ARR[i] <= ‘10^9’

Time Limit: 1 sec