시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 6 6 5 100.000%

## 문제

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