====== Binomial ======

===== 풀이 =====
  * 뤼카의 정리가 태그로 달려있어서 풀어보게 된 문제지만, 뤼카의 정리를 이용해서 이항계수를 직접 계산하는 문제는 아니다.
  * C(ai,aj)를 2로 나눈 나머지는, 뤼카의 정리를 사용해서 전개할 수 있다. C(ai,aj)%2를 구성하는 텀들은, ai와 aj를 각각 이진 전개한 뒤 각각의 자리수로 이항계수를 만든 것인데, 이는 C(1,1), C(1,0), C(0,1), C(0,0) 중에 하나이고, 이 중에서 C(0,1)을 제외하고는 모두 1이 된다. 이것들을 다 곱한 값이 홀수가 된다는 의미는 곱해지는 텀중에 C(0,1)이 없다는 뜻이고, 이는 ai와 aj를 각각 이진전개 하면 모든 자릿수에서 ai쪽이 aj쪽보다 크거나 같다, 즉 (ai|aj) = ai 라는 의미이다.
  * 모든 ai에 대해서 (ai|aj) = ai 인 aj의 갯수를 구하는 것은 dp로 계산 가능하다. [[:ps:다이나믹_프로그래밍#SOS dp]]방법을 사용하면 max(ai) 를 N이라고 할때, O(NlogN)에 계산할 수 있다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 18719. Binomial".

- Problem link: https://www.acmicpc.net/problem/18719
- Solution link: http://www.teferi.net/ps/problems/boj/18719

To get AC, this code should be submitted with PyPy3, not Python3.
"""


def main():
    z = int(input())
    for _ in range(z):
        n = int(input())  # pylint: disable=unused-variable
        a = [int(x) for x in input().split()]
        max_a = max(a)
        count = [0] * (max_a + 1)
        for a_i in a:
            count[a_i] += 1

        for i in range(max_a.bit_length() + 1):
            for num in range(max_a + 1):
                if num & (1 << i):
                    count[num] += count[num ^ (1 << i)]

        print(sum(count[a_i] for a_i in a))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_1}}