Read problems statements in mandarin chinese, russian and vietnamese as well. 

You are given N integers: A_{1}, A_{2}, ..., A_{N}. You need to count the number of pairs of indices (i, j) such that 1 ≤ i < j ≤ N and A_{i} | A_{j} ≤ max(A_{i}, A_{j}).

Note: A_{i} | A_{j} refers to bitwise OR.

------ Input ------ 

The first line of the input contains an integer T, denoting the number of test cases. The description of each testcase follows.
The first line of each testcase contains a single integer: N
The second line of each testcase contains N integers: A_{1}, A_{2}, ..., A_{N}.

------ Output ------ 

For each test case, output a single line containing the answer for that test case.

------ Constraints ------ 

$1 ≤ T ≤  20$
$1 ≤ N ≤ 10^{6} $
$0 ≤ A_{i} ≤  10^{6}$
$1 ≤ Sum of N over all test cases ≤  10^{6} $

------ Subtasks ------ 

Subtask #1 (20 points):

$1 ≤ N ≤ 10^{3} $

Subtask #2 (80 points):

$Original constraints$

----- Sample Input 1 ------ 
1
3
1 2 3
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
There are three possible pairs of indices which satisfy 1 ? i j ? N: (1, 2), (1, 3) and (2, 3). Let us see which of those satisfy Ai | Aj ? max(Ai, Aj):

(1, 2): A1 | A2 = 1 | 2 = (01)2 | (10)2 = (11)2 = 3. But max(A1, A2) = max(1, 2) = 2, and 3 ? 2 is not correct. Hence this is not a valid pair.
(1, 3): A1 | A3 = 1 | 3 = (01)2 | (11)2 = (11)2 = 3. And max(A1, A3) = max(1, 3) = 3, and 3 ? 3 is correct. Hence this is a valid pair.
(2, 3): A2 | A3 = 2 | 3 = (10)2 | (11)2 = (11)2 = 3. And max(A2, A3) = max(2, 3) = 3, and 3 ? 3 is correct. Hence this is a valid pair.

So there are a total of 2 valid pairs, and hence the answer is 2.

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Bit manipulation


Solutions:
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	d = {}
	for i in range(n):
		if arr[i] not in d:
			d[arr[i]] = 1
		else:
			d[arr[i]] += 1
	ans = 0
	for A1 in d.keys():
		ans += d[A1] * (d[A1] - 1)
		for A2 in d.keys():
			if A1 != A2 and A1 | A2 <= max(A1, A2):
				ans += d[A1] * d[A2]
	print(ans // 2)


from collections import Counter
import sys
readline = sys.stdin.readline
T = int(readline())
for t in range(T):
	N = int(readline())
	A = list(map(int, readline().split()))
	C = Counter(A)
	cnt = [0] * (max(A) + 1)
	for (a, c) in C.items():
		cnt[a] += c
	for i in range(20):
		for bit in range(max(A) + 1):
			if bit >> i & 1:
				cnt[bit] += cnt[bit ^ 1 << i]
	ans = 0
	for (a, c) in C.items():
		ans += cnt[a] * c
	for c in C.values():
		ans -= c * (c + 1) // 2
	print(ans)