Longest Odd Sum Subsequence

You are given an array of integers. Your task is to find the length of the longest subsequence where every pair of consecutive elements has an odd sum. In other words, for any two consecutive elements a and b in the subsequence, the condition a+b is odd must be satisfied.

A subsequence is obtained by deleting some or no elements from the array without changing the order of the remaining elements.

Observation: The sum of two numbers is odd if and only if one of them is even and the other is odd. Therefore, an alternating sequence of even and odd numbers is required. If the array contains only even numbers or only odd numbers, then no valid subsequence (with at least one adjacent pair) can be formed, and the answer is 0.

The maximum length of such a subsequence is given by:

$$\text{answer} = \begin{cases} 0, & \text{if the array contains only even or only odd numbers} \\ 2\cdot\min(\#odd,\,#even), & \text{otherwise} \end{cases} $$

Note that the subsequence must contain at least two elements for the condition to apply.

inputFormat

The first line contains a single integer T (0 ≤ T ≤ 10⁴), the number of test cases.

Each test case consists of two lines:

• The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of elements in the array.
• The second line contains n space-separated integers representing the array elements (1 ≤ element ≤ 10⁹).

If T equals 0, there will be no test cases following.

outputFormat

For each test case, output a single integer on a new line: the length of the longest subsequence such that the sum of any two consecutive elements is odd.

## sample

2
5
1 2 3 4 5
4
2 4 6 8

4
0

</p>