Largest Alternating Subsequence

Problem Description:

Given an array of integers, your task is to determine the length of the longest contiguous subsequence where the parity of every two consecutive numbers strictly alternates. Formally, the subsequence should satisfy that if (a_i) is even then (a_{i+1}) must be odd, and vice versa.

If the array is empty, the answer is 0. Otherwise, initialize the count to 1 and, for each subsequent element, increment the count if its parity differs from its immediate predecessor.

For example, for the array ( [1, 2, 3, 4, 5] ), the output is 5 (since 1 is odd, 2 is even, 3 is odd, 4 is even, 5 is odd). For the array ( [2, 4, 6, 8] ), the output is 1 because all numbers have the same parity.

inputFormat

Input is read from standard input (stdin).

The first line contains an integer (T), representing the number of test cases. Each test case is described using two lines:
1. The first line contains a single integer (N), the number of elements in the sequence.
2. The second line contains (N) space-separated integers representing the sequence.

outputFormat

For each test case, output a single integer on a new line representing the length of the longest contiguous subsequence with strictly alternating parity.## sample

3
5
1 2 3 4 5
4
2 4 6 8
0

5
1
0