시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 245 | 142 | 79 | 49.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.
2 3 1 5 6 3 1 1 1
4 9