이항 계수
면접 대비시간 제한5초메모리 제한512 MB
수열이 주어질 때 이항계수 C(a_i, a_j)가 홀수가 되는 순서쌍 (i, j)의 개수를 루카스 정리의 비트 조건으로 센다.
문제
어떤 사람들은 문제를 풀 때 자세하고 다소 불필요한 이야기로 실제 과제가 가려져야만 만족한다. 당신이 그런 사람이라면 이 문제는 당신을 위한 것이 아니다.
음이 아닌 정수 수열 (a_1, a_2, \ldots, a_n)이 주어진다. (1 \le i, j \le n)이고 (\binom{a_i}{a_j})가 홀수인 순서쌍 ((i, j))의 개수를 구해야 한다.
(\binom{n}{k})는 (n)개의 물건 중에서 (k)개를 순서를 고려하지 않고 고르는 경우의 수이다. 특히 (n < k)이면 (\binom{n}{k} = 0)이다.
입력
첫째 줄에는 테스트 케이스의 수 (z)가 주어진다 ((1 \le z \le 10)). 각 테스트 케이스의 설명이 이어진다.
각 테스트 케이스의 첫째 줄에는 수열의 원소 수 (n)이 주어진다 ((1 \le n \le 10^6)).
둘째 줄에는 (n)개의 정수 (a_i)가 주어진다 ((1 \le a_i \le 10^6)). 이 값들이 수열의 원소이다.
출력
각 테스트 케이스마다 문제의 답을 나타내는 정수 하나를 한 줄에 출력한다.