## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Wednesday, 20 April 2022

Lav has an array $A$ of size $N$. He noticed that Chef is initially standing at the first index of the array.

While standing at the ${i}^{th}$ index $\left(1\le i of the array, Chef can perform the following types of jumps:

• $\mathtt{\text{Jump 1}}$: Jump to the immediate next index $j$ such that ${A}_{i}$ and ${A}_{j}$ have the same parity.
• $\mathtt{\text{Jump 2}}$: Jump to the immediate next index $j$ such that ${A}_{i}$ and ${A}_{j}$ have different parity.

Given that Chef can perform $\mathtt{\text{Jump 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 $T$, the number of test cases. Then the test cases follow.
• The first line of each test case contains a single integer $N$ - the size of the array $A$.
• The second line of each test case contains $N$ integers ${A}_{1},{A}_{2},\dots ,{A}_{N}$ - the elements of the array $A$.

### 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

• $1\le T\le 100$
• $2\le N\le {10}^{4}$
• $1\le {A}_{i}\le {10}^{9}$

### Sample Input 1

2
4
1 2 3 4
4
2 1 3 4


### Sample Output 1

2
1


### Explanation

Test Case $1$: The minimum number of jumps required by the Chef to reach the last index is $2$. Chef is initially standing at index $1$.

• Chef chooses $\mathtt{\text{Jump 2}}$ and jumps to index $2$ as it is the immediate next element with different parity.
• Chef chooses $\mathtt{\text{Jump 1}}$ and jumps to index $4$ as it is the immediate next element with the same parity.

Test Case $2$: The minimum number of jumps required by the Chef to reach the last index is $1$. Chef is currently standing at index $1$.

• Chef chooses $\mathtt{\text{Jump 1}}$ and jumps to index $4$ as it is the immediate next element with the same parity.