Maximum Even Product Subarray Length

You are given an array of integers. Your task is to determine the maximum length of a contiguous subarray such that the product of its elements is even. A product is even if and only if the subarray contains at least one even number.

If there is no even number present in the array, the result should be 0. Otherwise, the maximum length is the length of the whole array.

Note: a subarray is a contiguous part of an array.

inputFormat

The first line contains a single integer T, the number of test cases. Each test case consists of two lines. The first line of a test case contains an integer M, the length of the array. The second line contains M integers separated by spaces representing the array elements.

outputFormat

For each test case, output a single line containing one integer — the maximum subarray length where the product of its elements is even.## sample

3
5
1 3 5 7 9
6
2 4 1 5 3 7
4
3 5 7 8

0
6
4