Question
Evn Sum Subarray
Given an array A of size N, find the size of the largest subarray of A which has an even sum. For example, for the array [2, 1, 2] the answer is just 1 as the largest subarray with an even sum is [2].
Note that a subarray is a contiguous part of an array. For the array [1, 3, 2], some possible subarrays are [1], [2], [1, 3], [1, 3, 2]. However, [1, 2] is not a subarray for this array.
Input
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N - the size of the array.
- The next line contains N space-separated integers - A1, A2, ... , AN.
Constraints
1 ≤ T ≤ 50
1 ≤ N ≤ 50
1 ≤ Ai ≤ 104
Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N - the size of the array.
- The next line contains N space-separated integers - A1, A2, ... , AN.
Constraints
1 ≤ T ≤ 50
1 ≤ N ≤ 50
1 ≤ Ai ≤ 104
Output
For each test case, output on a new line, the size of the largest subarray with even sum.
Example
Sample Input
2
3
2 1 2
3
1 3 2
Sample Output
1
3
Explanation
Test case 1: The largest subarray with even sum is the subarray [2] having size 1.
Test case 2: The largest subarray with even sum is the subarray [1, 3, 2] having size 3.
2
3
2 1 2
3
1 3 2
Sample Output
1
3
Explanation
Test case 1: The largest subarray with even sum is the subarray [2] having size 1.
Test case 2: The largest subarray with even sum is the subarray [1, 3, 2] having size 3.