Longest Alternating Subarray

You are given an array of integers. Your task is to find the length of the longest contiguous subarray in which consecutive elements alternate between even and odd numbers.

Formally, for an array \(a_1, a_2, \dots, a_N\), find the maximum positive integer \(L\) such that there exists an index \(i\) with \(1 \le i \le N-L+1\) and for every \(j\) with \(i+1 \le j \le i+L-1\), \(a_{j-1}\) and \(a_j\) have opposite parity. If no alternating sequence exists, output 1 (since any single element is considered alternating).

Note: Two numbers are of opposite parity if one of them is even and the other is odd.

inputFormat

The input is given from standard input and has the following format:

• The first line contains an integer (T) (the number of test cases).
• For each test case, the first line contains an integer (N) (the number of elements in the array).
• The second line of each test case contains (N) space-separated integers representing the array elements.

outputFormat

For each test case, output a single line with one integer — the length of the longest contiguous subarray where consecutive elements alternate between even and odd.## sample

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

5
2