Find the Nice Subsequence

Problem Statement:

You are given T test cases. In each test case, you are provided an array of n integers. Your task is to determine whether the array contains at least one odd number and at least one even number. If it does, a "nice" subsequence of length 2 can be formed (one odd and one even element), so output 2. Otherwise, if all elements are either odd or even, output -1.

Formal Definition:

Let the array be \(a_1, a_2, \dots, a_n\). If there exists indices \(i, j\) such that \(a_i\) is odd and \(a_j\) is even (or vice versa), then a nice subsequence exists and its length is 2; otherwise, no such subsequence exists and you should output -1.

inputFormat

Input Format:

The first line contains an integer T, denoting the number of test cases.

For each test case, the first line contains an integer n (the number of elements in the array), followed by a second line with n space-separated integers.

outputFormat

Output Format:

For each test case, output a single line containing the integer 2 if there exists at least one odd and one even number in the array, or -1 otherwise.

## sample

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

2
-1

</p>