시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB2451427949.375%

문제

There are people that wont be happy with solving a problem, unless the actual task is obscured by an elaborate and somewhat unnecessary story. If you are one of these people, then this problem is NOT for you.

You are given a sequence of non-negative integers \(a_1, a_2, . . . , a_n\). You need to find the number of pairs \((i, j)\) such that \(1 \le i, j \le n\) and \(\binom{a_i}{a_j}\)is odd.

Note that \(\binom{n}{k}\) is the number of ways, disregarding order, that \(k\) objects can be chosen from among n objects. In particular, if \(n < k\) then \(\binom{n}{k} = 0\).

입력

The first line of input contains the number of test cases \(z\) (\(1 \le z \le 10\)). The descriptions of the test cases follow.

The first line of each test case contains the number of elements in the sequence \(n\) (\(1 \le n \le 10^6\)).

The second line contains \(n\) integers \(a_i\) (\(1 \le a_i \le 10^6\)) – the elements of the sequence.

출력

For each test case, output a single line which contains a single integer – the answer for the problem.

예제 입력 1

2
3
1 5 6
3
1 1 1

예제 출력 1

4
9