Minimum Grouping Based on Participant ID Parity

You are given a series of test cases. In each test case, you are provided with a list of participant IDs. Your task is to determine the minimum number of groups required such that if any two participants have IDs whose sum is even, they must be in the same group.

The sum of two integers is even if both integers are even or both are odd. Therefore, if a test case contains both even and odd IDs, you will need to arrange the participants into two groups; otherwise, if all IDs are either even or odd, only one group is needed.

Note: Input is read from standard input (stdin) and output is written to standard output (stdout).

inputFormat

The first line of the input contains an integer T, the number of test cases. Each test case consists of the following two lines:

• The first line contains an integer N, the number of participants.
• The second line contains N space-separated integers representing the participant IDs.

outputFormat

For each test case, print one integer on a separate line — the minimum number of groups required.

## sample

2
5
2 4 3 5 7
3
8 6 2

2
1

</p>