Longest Beautiful Subarray

You are given T test cases. For each test case, an integer n and an array of n integers are provided. A subarray is considered beautiful if its sum is even. Your task is to determine the length of the longest beautiful subarray that can be obtained by removing zero or more elements from the beginning or the end of the array (thus forming a contiguous subarray).

In other words, consider an array of length n. Let the index of the first even number be denoted by firstEven and the index of the last even number be denoted by lastEven (using 0-indexing). Then, if an even number exists in the array, the answer is computed as follows:

$$\text{answer} = \max(lastEven + 1,\, n - firstEven,\, n - lastEven - 1)\, . $$

If there is no even number in the array, then if n > 1 the answer is n - 1, otherwise it is 0.

Note: The input guarantees that n \ge 1.

inputFormat

The first line contains an integer T, the number of test cases.

Each test case consists of two lines:

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

outputFormat

For each test case, output a single integer in a separate line denoting the length of the longest beautiful subarray.

## sample

1
5
1 2 3 4 5

4

</p>