Longest Increasing Subsequence with Even Sum

You are given an array A of N integers. Your task is to determine the length of the longest strictly increasing subsequence whose sum is even. A subsequence is formed by deleting zero or more elements from the array without changing the order of the remaining elements.

If no such subsequence exists, output -1.

Note: An increasing subsequence means that for every consecutive pair of elements a and b in the subsequence, a < b. The sum of the subsequence must be even in order for it to be considered valid.

inputFormat

The first line contains an integer T, the number of test cases. Each test case consists of two lines. The first line of each test case contains an integer N, representing the number of elements in the array. The second line contains N space-separated integers, representing the array A.

outputFormat

For each test case, output a single line containing the length of the longest strictly increasing subsequence with an even sum. If no such subsequence exists, output -1.

## sample

2
5
3 2 5 8 4
4
1 3 5 7

3
-1

</p>