Even Product Subsets

You are given an integer N and an array of N integers. Your task is to count the number of subsets of the array with at least two elements such that the product of all selected numbers is even. A product is even if and only if at least one of its factors is even.

More formally, let \(n = N\) and let the array be \(a_1, a_2, \dots, a_n\). You need to count the number of subsets \(S \subseteq \{1, 2, \dots, n\}\) with \(|S| \ge 2\) such that \[ \prod_{i \in S} a_i \equiv 0 \pmod{2}. \]

If there is no even number in the array, the answer is 0.

inputFormat

The input is read from stdin and has the following format:

T
N1
a1 a2 ... aN1
N2
a1 a2 ... aN2
...
NT
a1 a2 ... aNT

Here, T is the number of test cases. For each test case, the first line is an integer N (the number of elements in the array), followed by a line of N space-separated integers.

outputFormat

For each test case, print on a separate line the number of valid subsets (subsets of size at least two) whose product is even. The output should be written to stdout.

## sample

4
3
1 2 3
4
5 7 11 2
4
1 3 5 7
4
1 2 4 6

3
7
0
11

</p>