Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

L. Terminal
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$.

You may repeatedly apply the following operation:

  • Select an index $$$i$$$ ($$$1 \le i \lt |a|$$$, where $$$|a|$$$ denotes the current length of $$$a$$$) such that $$$a_i + a_{i+1}$$$ is odd, and delete $$$a_i$$$. As a result, the elements after index $$$i$$$ shift one position to the left.

You must keep applying the operation until there is no valid index where the operation can be applied. That is, you must apply the operation until no two adjacent elements in the array sum up to an odd number. The resulting array is called terminal. Depending on the order in which you perform the operations, you can end up with different terminal arrays.

Consider every terminal array reachable from $$$a$$$ through some sequence of operations. Determine how many distinct lengths these terminal arrays can have.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$)  — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$)  — the length of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)  — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output a single integer  — the number of distinct lengths a terminal array reachable from $$$a$$$ can have.

Example
Input
2
3
3 5 7
4
1 2 3 4
Output
1
2
Note

In the first test case, every adjacent pair sums up to an even number, so no operation can be performed. The array is already terminal, and the only reachable length is $$$3$$$.

In the second test case, different orders of operations can leave arrays of different lengths. For instance:

  • delete $$$a_1 = 1$$$ (since $$$1 + 2 = 3$$$ is odd) to get $$$[2, 3, 4]$$$, then delete $$$a_1 = 2$$$ (since $$$2 + 3 = 5$$$ is odd) to get $$$[3, 4]$$$, then delete $$$a_1 = 3$$$ (since $$$3 + 4 = 7$$$ is odd) to get $$$[4]$$$, which is terminal with length $$$1$$$;
  • delete $$$a_3 = 3$$$ (since $$$3 + 4 = 7$$$ is odd) to get $$$[1, 2, 4]$$$, then delete $$$a_1 = 1$$$ (since $$$1 + 2 = 3$$$ is odd) to get $$$[2, 4]$$$, which is terminal with length $$$2$$$.

Only lengths $$$1$$$ and $$$2$$$ can be reached, so the answer is $$$2$$$.