Longest Same Parity Subsequence

Given a series of numbers, determine the length of the longest contiguous subsequence where every pair of adjacent numbers have the same parity. Two numbers have the same parity if both are even or both are odd. In mathematical terms, for any two adjacent numbers \(a\) and \(b\), the condition is satisfied if \(a \bmod 2 = b \bmod 2\).

You are given \(T\) test cases. For each test case, you first receive an integer \(N\) (the length of the sequence) followed by \(N\) integers. Your task is to compute and output the length of the longest contiguous subsequence that satisfies the parity condition for each test case.

inputFormat

The first line of the input contains an integer \(T\), the number of test cases. For each test case, the input is given in the following format:

N
a1 a2 ... aN

Here, \(N\) denotes the number of integers in the sequence, and \(a₁, a₂, \ldots, a_N\) represent the sequence of integers.

outputFormat

For each test case, output a single integer representing the length of the longest contiguous subsequence where every pair of adjacent numbers has the same parity. Each output should be on a separate line.

1
5
1 2 4 6 5

3