Lav has an array AA of size NN. He noticed that Chef is initially standing at the first index of the array.

While standing at the ithith index (1i<N)(1≤i<N) of the array, Chef can perform the following types of jumps:

• Jump 1Jump 1: Jump to the immediate next index jj such that AiAi and AjAj have the same parity.
• Jump 2Jump 2: Jump to the immediate next index jj such that AiAi and AjAj have different parity.

Given that Chef can perform Jump 2Jump 2 at most once, Lav wants to find the minimum number of jumps required by the Chef to reach the last index of the array.

### Input Format

• First line will contain TT, the number of test cases. Then the test cases follow.
• The first line of each test case contains a single integer NN – the size of the array AA.
• The second line of each test case contains NN integers A1,A2,,ANA1,A2,…,AN – the elements of the array AA.

### Output Format

For each test case, output the minimum number of jumps required by the Chef to reach the last index of the array.

### Constraints

• 1T1001≤T≤100
• 2N1042≤N≤104
• 1Ai1091≤Ai≤109

### Sample Input 1

2
4
1 2 3 4
4
2 1 3 4


### Sample Output 1

2
1