Maximum Non-Adjacent Even Count

You are given an array of integers. Your task is to select as many even numbers as possible from the array under the constraint that no two selected even numbers are adjacent in the original array order. In other words, if you pick an even number from the array, you cannot pick its immediate neighbors even if they are even.

This problem can be tackled using dynamic programming. Define the recurrence as follows:

$$dp[i] = \begin{cases} \max(dp[i-1], dp[i-2] + 1) & \text{if } arr[i] \text{ is even}, \\ dp[i-1] & \text{if } arr[i] \text{ is odd}, \end{cases} $$

with appropriate base cases. The answer for each test case is given by \(dp[n]\), where \(n\) is the size of the array.

Note: The input and output are managed via stdin and stdout, respectively.

inputFormat

The input begins with an integer T representing the number of test cases. Each test case consists of the following two lines:

• The first line contains an integer N representing the size of the array.
• The second line contains N space-separated integers representing the elements of the array.

Constraints:

• \(1 \le T \le 10\)
• \(1 \le N \le 10^5\)
• \(0 \le A[i] \le 10^9\)

outputFormat

For each test case, output a single line with a single integer which is the maximum number of even numbers that can be selected from the array such that no two selected numbers are adjacent.

## sample

1
5
1 3 5 7 9

0

</p>