Alice has an array A of length N. She is interested in finding the number of pairs (i, j) such that 1≤ i < j ≤ N and A_{i} \oplus A_{j} < A_{i} \& A_{j}.

\oplus represents the [Bitwise XOR] operator.
\& represents the [Bitwise AND] operator.

------ Input Format ------ 

- The first line of input will contain an integer T — number of test cases. Then the test cases follow.
- Each test case contains two lines of input.
- The first line of each test case contains an integer N, the length of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots , A_{N}. 

------ Output Format ------ 

For each test case, output the number of pairs (i, j) such that 1 ≤ i < j ≤ N and A_{i} \oplus A_{j} < A_{i} \& A_{j}. 

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
4
1 1 2 3
4
1 2 3 4
----- Sample Output 1 ------ 
2
1
----- explanation 1 ------ 
Test case $1$: The two pairs of indices satisfying the condition are $(1, 2)$ and $(3, 4)$, because
- $A_{1} \oplus A_{2} = 0$ and $A_{1} \& A_{2} = 1$
- $A_{3} \oplus A_{4} = 1$ and $A_{3} \& A_{4} = 2$

Test case $2$: The only pair of indices satisfying the condition is $(2, 3)$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics


Solutions:
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	if n == 1:
		print(1)
	else:
		c = 0
		ans = 0
		ch = 1
		for i in range(n):
			if arr[i] <= 2 ** ch - 1:
				c += 1
			else:
				ans += c * (c - 1) // 2
				c = 1
				ch += 1
		if c > 1:
			ans += c * (c - 1) // 2
		print(ans)


def log2(a):
	k = 0
	while a // 2:
		a //= 2
		k += 1
	return k

def s(k):
	return k * (k - 1) // 2
for t in range(int(input())):
	input()
	l = list(map(int, input().split()))
	k = 0
	d = {}
	for i in l:
		a = log2(i)
		if a in d:
			d[a] += 1
		else:
			d[a] = 1
	for i in d:
		k += s(d[i])
	print(k)


import sys
from math import gcd, sqrt, log2, ceil, floor
tc = int(input().strip())
for t in range(tc):
	n = int(input().strip())
	arr = list(map(int, input().split()))
	count = [0] * 32
	for i in arr:
		count[int(log2(i))] += 1
	ans = 0
	for i in count:
		ans += i * (i - 1) // 2
	print(ans)


import math
for _ in range(int(input())):
	N = int(input())
	mainArray = list(map(int, input().split()))
	mainArray.sort()
	flag = 0
	MSB = -1
	counter = 1
	Sum = 0
	for i in range(N):
		if MSB != -1:
			MSB2 = int(math.log2(mainArray[i]))
			if MSB != MSB2:
				Sum += int(counter * (counter - 1) / 2)
				counter = 1
				MSB = MSB2
			else:
				counter += 1
		else:
			MSB = int(math.log2(mainArray[i]))
	if counter > 1:
		Sum += int(counter * (counter - 1) / 2)
	print(Sum)


def soln(n, arr):
	counts = [0] * 33
	for i in arr:
		for j in range(1, 33):
			if i < 1 << j:
				counts[j] += 1
				break
	calc = lambda x: x * (x + 1) // 2
	res = 0
	for count in counts:
		res += calc(count - 1)
	return res
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(soln(n, arr))


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = [0] * 32
	for x in a:
		count[int(math.log2(x))] += 1
	ans = 0
	for x in count:
		ans += int((x * x - x) / 2)
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	d = defaultdict(lambda : 0)
	for i in A:
		z = str(bin(i))
		d[len(z)] += 1
	c = 0
	for i in d:
		c += d[i] * (d[i] - 1) // 2
	print(c)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	d = {}
	for i in arr:
		p = 1
		b = 0
		while i != 0:
			if i & 1 != 0:
				b = p
			p *= 2
			i >>= 1
		if d.get(b) is None:
			d[b] = 1
		else:
			d[b] += 1
	c = 0
	for i in d:
		c += d[i] * (d[i] - 1) // 2
	print(c)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	for i in range(n):
		b.append(len(bin(a[i])[2:]))
	c = Counter(b)
	res = 0
	for x in c.values():
		res += x * (x - 1) // 2
	print(res)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	a.sort()
	x = 1
	c = 0
	ans = 0
	i = 0
	while i != n:
		if a[i] < 2 * x:
			c += 1
		else:
			x *= 2
			ans += c * (c - 1) // 2
			c = 1
		i += 1
	print(ans + c * (c - 1) // 2)


from math import log2
for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	q = [0] * 32
	for i in a:
		q[int(log2(i))] += 1
	ans = 0
	for i in q:
		if i > 1:
			ans += (i - 1) * i // 2
	print(ans)


from typing import Counter
for _ in range(int(input())):
	n = int(input())
	ali = list(map(int, input().split()))
	bli = list()
	for a in ali:
		bli.append(len(bin(a)))
	cnt = Counter(bli)
	ans = 0
	for el in cnt.values():
		ans += el * (el - 1) // 2
	print(ans)


from collections import Counter

def find(num):
	i = 0
	while num > 0:
		num = num >> 1
		i += 1
	return i

def solve(n, arr):
	res = 0
	lookup = Counter()
	for num in arr:
		msb_set = find(num)
		res += lookup[msb_set]
		lookup[msb_set] += 1
	return res
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


mod = 1000000007
read_int = lambda : int(input().strip())
read_str = lambda : input().strip()
read_str_arr = lambda : input().strip().split()
read_int_arr = lambda : [int(x) for x in input().strip().split()]
from math import floor, log2

def solve():
	N = read_int()
	A = read_int_arr()
	msb_dict = {}
	for x in A:
		msb_pos = floor(log2(x))
		if msb_pos in msb_dict:
			msb_dict[msb_pos] += 1
		else:
			msb_dict[msb_pos] = 1
	ans = 0
	for x in msb_dict.values():
		ans += x * (x - 1) // 2
	print(ans)
for _ in range(int(input())):
	solve()


import math
t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	ans = 0
	for i in range(n):
		lg = int(math.log2(arr[i]))
		try:
			d[lg] += 1
		except:
			d[lg] = 1
	for (key, value) in d.items():
		ans += value * (value - 1) // 2
	print(ans)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	check = [0 for _ in range(32)]
	for _ in range(N):
		check[A[_].bit_length()] += 1
	res = int(sum([n * (n - 1) / 2 for n in check]))
	print(res)


import math
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	dic = defaultdict(int)
	for x in l:
		log = math.floor(math.log2(x))
		dic[log] += 1
	ans = 0
	for x in dic:
		s = dic[x]
		ans += s * (s - 1) // 2
	print(ans)


def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		A = [int(x) for x in input().split()]
		counts = [0 for _ in range(32)]
		for a in A:
			counts[a.bit_length()] += 1
		res = sum([n * (n - 1) // 2 for n in counts])
		print(res)
main()


t = int(input())
for i in range(t):
	a = int(input())
	b = list(map(int, input().split()))
	li = [0] * 32
	ans = 0
	for j in range(a):
		g = b[j]
		cnt = 0
		while g:
			g = g >> 1
			cnt += 1
		li[cnt] += 1
	for j in range(32):
		ans = ans + li[j] * (li[j] - 1) // 2
	print(ans)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	left_ptr = 0
	ans = 0
	count = 1
	right_ptr = left_ptr + 1
	while right_ptr < n:
		if arr[left_ptr] ^ arr[right_ptr] < arr[left_ptr] & arr[right_ptr]:
			ans += count
			count += 1
		else:
			count = 1
			left_ptr = right_ptr
		right_ptr += 1
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = {}
	for i in a:
		f = int(math.log2(i)) + 1
		if f in m.keys():
			m[f] += 1
		else:
			m[f] = 1
	ans = 0
	for (key, val) in m.items():
		ans += val * (val - 1) // 2
	print(ans)


import math

def nCr(n, r):
	return fact(n) / (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	j = [0] * 40
	for i in l:
		if i == 1:
			j[0] = j[0] + 1
		else:
			g = math.floor(math.log(i, 2))
			j[g] = j[g] + 1
	ans = 0
	for i in j:
		if i > 1:
			ans = ans + int(i * (i - 1) / 2)
	print(ans)


def pairs(arr, size):
	if size == 1:
		return 0
	else:
		arr.sort()
		i = 0
		j = 1
		count = 0
		while i < size:
			check1 = arr[i] ^ arr[j]
			check2 = arr[i] & arr[j]
			if check2 > check1:
				if j + 1 == size:
					n = j - i + 1
					count += n * (n - 1) / 2
					return int(count)
				else:
					j += 1
			else:
				n = j - i
				count += n * (n - 1) / 2
				if j == size - 1:
					return int(count)
				else:
					i = j
					j += 1
		return int(count)
test_cases = int(input())
while test_cases != 0:
	d = int(input())
	data = list(map(int, input().split()))
	print(pairs(data, d))
	test_cases -= 1


import collections

def getMSB(A):
	arr = []
	for n in A:
		if n == 0:
			arr.append(0)
			continue
		msb = 0
		n = n // 2
		while n > 0:
			n = n // 2
			msb += 1
		arr.append(msb)
	lookup = collections.Counter(arr)
	ans = 0
	for item in lookup:
		ans += lookup[item] * (lookup[item] - 1) // 2
	return ans

def main():
	T = int(input())
	for i in range(T):
		N = int(input())
		A = list(map(int, input().split(' ')))
		val = getMSB(A)
		print(val)
main()


import math
from collections import defaultdict
for i in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	dic = defaultdict(int)
	for i in l:
		dic[math.floor(math.log(i, 2)) + 1] += 1
	ans = 0
	for i in dic:
		ans += dic[i] * (dic[i] - 1) / 2
	print(int(ans))


import math
for i in range(int(input())):
	n = int(input())
	l = []
	a = [int(x) for x in input().split()]
	for i in a:
		s = len(bin(i)[2:])
		l.append(s)
	count = 1
	l.sort()
	c = 0
	for i in range(1, n):
		if l[i] == l[i - 1]:
			count += 1
		else:
			c = c + count * (count - 1) // 2
			count = 1
	c += count * (count - 1) // 2
	print(c)


def getmsb(k):
	msb = 0
	if k == 0:
		return msb
	while k != 0:
		k = k // 2
		msb += 1
	return msb - 1
for _ in range(int(input())):
	n = int(input())
	msb = {}
	a = list(map(int, input().split()))
	for i in range(n):
		k = getmsb(a[i])
		msb[k] = msb.get(k, 0) + 1
	pairs = 0
	for val in msb.values():
		if val > 1:
			pairs += val * (val - 1) // 2
	print(pairs)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [bin(int(s))[2:] for s in input().split(' ')]
	bits = [0] * 33
	for num in a:
		l = len(num)
		bits[l] += 1
	ans = 0
	for i in range(33):
		if bits[i]:
			b = bits[i]
			val = b * (b - 1) // 2
			ans += val
	print(ans)


for i in range(int(input())):
	k = dict()
	final = 0
	_ = int(input())
	vals = list(map(int, input().split()))
	for i in range(len(vals)):
		vals[i] = len(bin(vals[i])) - 2
	for j in vals:
		if j in k:
			k[j] += 1
		else:
			k[j] = 1
	for l in k.values():
		final += l * (l - 1) // 2
	print(final)


try:

	def getMSB(n):
		if n == 0:
			return 0
		msb = 0
		n //= 2
		while n != 0:
			n //= 2
			msb += 1
		return msb
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		msbCount = [0] * 32
		for i in range(n):
			msb = getMSB(arr[i])
			msbCount[msb] += 1
		pairs = 0
		for i in range(n):
			msb = getMSB(arr[i])
			pairs += max(0, msbCount[msb] - 1)
		print(pairs // 2)
except:
	pass


for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	dic = {}
	for a in A:
		l = len(bin(a)) - 2
		dic[l] = dic[l] + 1 if l in dic else 0
	print(sum((dic[l] * (dic[l] + 1) // 2 for l in dic)))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	(memo, tp) = ({}, 1)
	for i in a:
		if tp & i < tp * 2 & i:
			tp *= 2
		memo[tp] = memo.get(tp, 0) + 1
	count = 0
	for v in memo.values():
		count += v * (v - 1) // 2
	print(count)


def size(x):
	result = 0
	while x > 0:
		x //= 2
		result += 1
	return result
T = int(input())
for t in range(T):
	N = int(input())
	A = [int(a) for a in input().split()]
	B = {}
	for a in A:
		temp = size(a)
		if temp in B.keys():
			B[temp] += 1
		else:
			B[temp] = 1
	count = 0
	for b in B.values():
		count += b * (b - 1) // 2
	print(count)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	s = 0
	c = 1
	x = 1
	for i in range(n):
		while a[i] >= x:
			x *= 2
			c = 1
		s += c - 1
		c += 1
	print(s)


def findmsb(n):
	msb = 0
	n = n // 2
	while n != 0:
		n //= 2
		msb += 1
	return msb

def factorial(n):
	p = 1
	for i in range(1, n + 1):
		p *= i
	return p
n = int(input())
for i in range(n):
	k = int(input())
	l = input().split()
	msb = [0 for j in range(32)]
	p = []
	for j in l:
		m = findmsb(int(j))
		p.append(m)
		msb[m] += 1
	count = 0
	for j in p:
		count += max(msb[j] - 1, 0)
	print(count // 2)


from math import *

def binomial_coefficient(n, r):
	if n == 1:
		return 0
	if r > n - r:
		r = n - r
	res = 1
	for i in range(r):
		res = res * (n - i)
		res = res // (i + 1)
	return res
t = int(input())
for z in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ans = 0
	mp = {}
	for i in range(len(arr)):
		a = int(log(arr[i], 2))
		try:
			mp[a]
			mp[a] += 1
		except:
			mp[a] = 1
	ans = 0
	for el in mp:
		ans += binomial_coefficient(mp[el], 2)
	print(int(ans))


t = int(input())
for i in range(0, t):
	n = int(input())
	lst = list(map(int, input().split()))
	lst1 = [0] * 60
	cnt = 0
	for i in lst:
		x = len(bin(i).replace('0b', '')) - 1
		lst1[x] = lst1[x] + 1
	for i in lst1:
		cnt = cnt + i * (i - 1) // 2
	print(cnt)


import math
T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	arr = arr[:N]
	res = 0
	bits = [0] * 32
	for i in range(N):
		val = int(math.log2(arr[i]))
		res += bits[val]
		bits[val] += 1
	print(res)


from collections import defaultdict

def msbPosition(n):
	i = 0
	while n > 0:
		i += 1
		n >>= 1
	return i + 1

def main(arr):
	d = defaultdict(lambda : 0)
	for a in arr:
		d[msbPosition(a)] += 1
	print(sum((i * (i - 1) // 2 for i in d.values() if i >= 2)))
for _ in range(int(input())):
	n = int(input())
	arr = map(int, input().split())
	main(arr)


def binary(num):
	count = 0
	while num:
		num = num // 2
		count += 1
	return count
t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	a = {}
	for item in b:
		if binary(item) in a:
			a[binary(item)] += 1
		else:
			a[binary(item)] = 1
	ans = 0
	for (key, value) in a.items():
		if value > 1:
			ans += value * (value - 1) // 2
	print(ans)


def mergesort(list):
	if len(list) > 1:
		mid = len(list) // 2
		l = list[:mid]
		r = list[mid:]
		mergesort(l)
		mergesort(r)
		(i, j, k) = (0, 0, 0)
		while i < len(l) and j < len(r):
			if l[i] <= r[j]:
				list[k] = l[i]
				i += 1
			else:
				list[k] = r[j]
				j += 1
			k += 1
		while i < len(l):
			list[k] = l[i]
			k += 1
			i += 1
		while j < len(r):
			list[k] = r[j]
			j += 1
			k += 1
		return

def binary(num):
	count = 0
	while num:
		num = num // 2
		count += 1
	return count
t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	mergesort(b)
	a = {}
	for item in b:
		if binary(item) in a:
			a[binary(item)] += 1
		else:
			a[binary(item)] = 1
	ans = 0
	for (key, value) in a.items():
		if value > 1:
			ans += value * (value - 1) // 2
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = defaultdict(lambda : 0)
	for i in a:
		d[len(bin(i)) - 2] += 1
	s = 0
	for i in d:
		s += d[i] * (d[i] - 1) // 2
	print(s)


import math as mt
T = int(input())
for t in range(T):
	N = int(input())
	X = list(map(int, input().split()))
	dt = {}
	for i in range(N):
		if X[i] == 1:
			if 0 in dt:
				dt[0] = dt[0] + 1
			else:
				dt[0] = 1
		else:
			r = mt.log(X[i], 2)
			r1 = int(r)
			if r1 in dt:
				dt[r1] = dt[r1] + 1
			else:
				dt[r1] = 1
	sm = 0
	for j in dt:
		if dt[j] > 1:
			m = dt[j]
			sm = sm + m * (m - 1) // 2
	print(sm)


import numpy, math
T = int(input())
for i in range(T):
	N = int(input())
	values = list(map(int, input().split(' ')))
	A = numpy.array(values)
	A = numpy.sort(A)
	A = numpy.floor(numpy.log2(A))
	count = 0
	subcount = 0
	start = 0
	for i in range(N):
		if A[i] > start:
			count += subcount * (subcount - 1) // 2
			subcount = 1
			start = A[i]
		else:
			subcount += 1
	count += subcount * (subcount - 1) // 2
	print(count)


import sys
import math
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	arr = [int(i) for i in input().split()]
	res = 0
	bit = [0] * 32
	for i in range(0, n):
		pos = int(math.log(arr[i], 2))
		bit[pos] = bit[pos] + 1
	for i in range(0, 32):
		res = res + int(bit[i] * (bit[i] - 1) / 2)
	res = int(n * (n - 1) / 2 - res)
	print(int(n * (n - 1) / 2 - res))


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	dp = []
	for i in nums:
		dp.append(len(bin(i)))
	res = Counter(dp)
	ans = 0
	for value in res.values():
		ans += value * (value - 1) // 2
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	c = [0] * 40
	for x in map(int, input().split()):
		i = 0
		while x > 0:
			x >>= 1
			i += 1
		c[i] += 1
	d = 0
	for x in c:
		d += x * (x - 1)
	print(d >> 1)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		s = 0
		while i > 0:
			s += 1
			i //= 2
		if s in d:
			d[s] += 1
		else:
			d[s] = 1
	ts = 0
	for i in d:
		ts += d[i] * (d[i] - 1) // 2
	print(ts)


from math import factorial

def get_msb(i):
	msb = 0
	while i:
		i >>= 1
		msb += 1
	return msb

def comb(n, k):
	if k > n:
		return 0
	return int(factorial(n) / (factorial(k) * factorial(n - k)))
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	p = 0
	for i in a:
		k = get_msb(i)
		if k in d:
			d[k] += 1
		else:
			d[k] = 1
	for (k, v) in d.items():
		if k:
			p += comb(v, 2)
	print(p)


def getting(n):
	return bin(n).replace('0b', '')
t = int(input())
for i in range(t):
	result = {}
	n = int(input())
	li = list(map(int, input().split()))
	for i in li:
		s = getting(i)
		le = len(s)
		for i in range(le):
			if s[i] == '1':
				if le - i in result:
					result[le - i].append(s)
				else:
					result[le - i] = [s]
				break
	count = 0
	for i in result:
		a = len(result[i])
		count += a * (a - 1) // 2
	print(count)


for _ in range(int(input())):
	N = int(input())
	arr = [int(x) for x in input().split()]

	def getMSB(num):
		if num == 0:
			return 0
		else:
			msb = 0
			num = num // 2
			while num != 0:
				num = num // 2
				msb += 1
			return msb
	msb_count = {}
	for i in range(32):
		msb_count[i] = 0
	for i in arr:
		msb_count[getMSB(i)] += 1
	pairs = 0
	for i in msb_count:
		pairs += msb_count[i] * (msb_count[i] - 1) // 2
	print(pairs)


from math import log2
p = lambda a: print(a)
iip = lambda : int(input())
sip = lambda : input()
mip = lambda : map(int, input().strip().split())
lip = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
flr = lambda x: int(x)
tstcs = lambda : range(int(input()))
for t in tstcs():
	n = iip()
	l = lip()
	l.sort()
	l1 = []
	c = 0
	m = ceil(log2(l[-1] + 1))
	for i in l:
		l1.append(ceil(log2(i + 1)))
	for j in range(1, m + 1):
		y = l1.count(j) - 1
		c = c + int(y * (y + 1) / 2)
	print(c)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	bit = [0] * 30
	ans = 0
	for i in range(n):
		l = math.log(a[i], 2)
		ans += bit[int(l)]
		bit[int(l)] += 1
	print(ans)


import itertools
import heapq
import collections
import math
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def inis():
	return input().split()

def stlt():
	return list(map(str, input().split()))

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	l = []
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			l.append(p)
		else:
			continue
	return l

def isPrime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return False

def gcdofarray(a):
	x = 0
	for p in a:
		x = math.gcd(x, p)
	return x

def printDivisors(n):
	i = 1
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				ans.append(i)
			else:
				ans.append(i)
				ans.append(n // i)
		i = i + 1
	ans.sort()
	return ans

def CountDivisors(n):
	i = 1
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n / i == i:
				ans.append(i)
			else:
				ans.append(i)
				ans.append(n // i)
		i = i + 1
	ans.sort()
	return len(ans)

def binaryToDecimal(n):
	return int(n, 2)

def countTriplets(a, n):
	s = set()
	for i in range(n):
		s.add(a[i])
	count = 0
	for i in range(n):
		for j in range(i + 1, n, 1):
			xr = a[i] ^ a[j]
			if xr in s and xr != a[i] and (xr != a[j]):
				count += 1
	return int(count // 3)

def generate_twin_prime(n):
	a = 0
	for i in range(1, n + 1):
		j = i + 2
		if isPrime(i) and isPrime(j):
			if 2 ^ (i ^ j) == 0:
				a += 1
	return a

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def countOdd(L, R):
	N = (R - L) // 2
	if R % 2 != 0 or L % 2 != 0:
		N += 1
	return N

def isPalindrome(s):
	return s == s[::-1]

def sufsum(test_list):
	test_list.reverse()
	res = [sum(test_list[:i + 1]) for i in range(len(test_list))]
	return res

def prsum(lst):
	return list(itertools.accumulate(lst))

def badachotabadachota(nums):
	nums.sort()
	i = 0
	j = len(nums) - 1
	ans = []
	cc = 0
	while len(ans) != len(nums):
		if cc % 2 == 0:
			ans.append(nums[j])
			j -= 1
		else:
			ans.append(nums[i])
			i += 1
		cc += 1
	return ans

def primeFactors(n):
	ans = []
	while n % 2 == 0:
		ans.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			ans.append(i)
			n = n / i
	if n > 2:
		ans.append(n)
	return ans

def closestMultiple(n, x):
	if x > n:
		return x
	z = int(x / 2)
	n = n + z
	n = n - n % x
	return n

def can_form_palindrome(arr, n):
	MAX = 256
	s = ''
	for i in range(n):
		s = s + str(arr[i])
	freq = [0] * MAX
	for i in range(n):
		freq[arr[i]] = freq[arr[i]] + 1
	count = 0
	for i in range(MAX):
		if freq[i] & 1:
			count = count + 1
		if count > 1:
			return False
	return True

def getPairsCount(arr, n, sum):
	m = [0] * 1000
	for i in range(0, n):
		m[arr[i]] += 1
	twice_count = 0
	for i in range(0, n):
		twice_count += m[int(sum - arr[i])]
		if int(sum - arr[i]) == arr[i]:
			twice_count -= 1
	return int(twice_count / 2)

def remove_consec_duplicates(test_list):
	res = [i[0] for i in itertools.groupby(test_list)]
	return res

def BigPower(a, b, mod):
	if b == 0:
		return 1
	ans = BigPower(a, b // 2, mod)
	ans *= ans
	ans %= mod
	if b % 2:
		ans *= a
	return ans % mod

class Graph:

	def __init__(self, edges, n):
		self.adjList = [[] for _ in range(n)]
		for (src, dest) in edges:
			self.adjList[src].append(dest)
			self.adjList[dest].append(src)

def BFS(graph, v, discovered):
	q = collections.deque()
	discovered[v] = True
	q.append(v)
	ans = []
	while q:
		v = q.popleft()
		ans.append(v)
		for u in graph.adjList[v]:
			if not discovered[u]:
				discovered[u] = True
				q.append(u)
		return ans
alphabets = list('abcdefghijklmnopqrstuvwxyz')
for _ in range(inp()):
	n = inp()
	a = inlt()
	a.sort()
	b = [bin(i).replace('0b', '') for i in a]
	ans = 0
	i = 0
	d = {}
	while i < n:
		if len(b[i]) in d:
			d[len(b[i])] += 1
		else:
			d[len(b[i])] = 1
		i += 1
	for i in d:
		t = d[i]
		ans += t * (t - 1) // 2
	print(ans)


mod = 1000000007
from sys import stdin, stdout
input = stdin.readline
from collections import defaultdict, Counter, deque
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		li[i] = len(bin(li[i])[2:])
	dic = Counter(li)
	for ele in dic.values():
		ans += ele * (ele - 1) // 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = []
	x = '1'
	t = 0
	for i in range(len(l1)):
		if l1[i] == 1:
			t += 1
	while int(x, 2) <= max(l1):
		l2.append(int(x, 2))
		x += '1'
	total = 0
	for i in range(1, len(l2)):
		count = 0
		for j in range(len(l1)):
			if l2[i - 1] < l1[j] <= l2[i]:
				count += 1
		total += count * (count - 1) // 2
	count = 0
	for j in range(len(l1)):
		if l1[j] > l2[len(l2) - 1]:
			count += 1
	total += count * (count - 1) // 2
	print(total + t * (t - 1) // 2)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mp = {w: 0 for w in range(1, 32 + 1)}
	for x in a:
		mp[len('{0:b}'.format(x))] += 1
	uwu = 0
	for (_, v) in mp.items():
		uwu += v * (v - 1) // 2
	print(uwu)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	visited = [False] * n
	for b in range(32, -1, -1):
		c = 0
		for i in range(n):
			if visited[i]:
				continue
			if a[i] >> b & 1:
				visited[i] = True
				c += 1
		ans += c * (c - 1) >> 1
	print(ans)


ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
m = 10 ** 9 + 7
inp = lambda : int(input())
for _ in range(inp()):
	n = inp()
	arr = ints()
	count = 0
	d = {}
	for x in arr:
		bn = bin(x)[2:]
		bin_length = len(bn)
		bn = (30 - bin_length) * '0' + bn
		first_occur = bn.index('1')
		if bn.index('1') in d:
			d[first_occur] += 1
			count += d[first_occur]
		else:
			d[first_occur] = 0
	print(count)


ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
m = 10 ** 9 + 7
inp = lambda : int(input())

def custom_call(arr, n, i):
	ct = 0
	for j in range(i + 1, n):
		(x, y) = (arr[i], arr[j])
		if x ^ y < x & y:
			ct += 1
	return ct
for _ in range(inp()):
	n = inp()
	arr = ints()
	s = set(arr)
	mn = min(arr)
	mx = max(arr)
	count = 0
	d = {}
	for (i, x) in enumerate(arr):
		bn = bin(x)[2:]
		bin_length = len(bn)
		bn = (30 - bin_length) * '0' + bn
		first_occur = bn.index('1')
		if bn.index('1') in d:
			d[first_occur] += 1
			count += d[first_occur] - 1
		else:
			d[first_occur] = 1
	print(count)


def get_msb(n):
	num = bin(n)[2:]
	for i in range(len(num)):
		if num[i] == '1':
			return len(num) - i
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	pos = [get_msb(arr[i]) for i in range(n)]
	bits = [0 for i in range(32)]
	for i in range(n):
		bits[pos[i] - 1] += 1
	count = 0
	for i in range(32):
		if bits[i] >= 2:
			count += bits[i] * (bits[i] - 1) // 2
	print(count)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	pos = []
	for i in l:
		p = bin(i)
		q = str(p)
		r = len(q) - 2
		pos.append(r)
	m = Counter(pos)
	ans = 0
	for i in set(pos):
		p = m[i]
		q = (p - 1) * p / 2
		ans += q
	print(int(ans))


def getmsb(n):
	msb = 0
	n = n // 2
	while n != 0:
		n //= 2
		msb += 1
	return msb
t = int(input())
for i in range(1, t + 1):
	n = int(input())
	arr = list(map(int, input().split()))
	msbc = [0 for i in range(0, 32 + 1)]
	for i in arr:
		msb = getmsb(i)
		msbc[msb] += 1
	pairs = 0
	for i in arr:
		ms = getmsb(i)
		pairs += max(0, msbc[ms] - 1)
	print(pairs // 2)


from math import ceil, gcd, factorial, sqrt, log, log2
import queue
from itertools import permutations, combinations, accumulate, product
from collections import Counter, deque
from sys import stdin, stdout
from bisect import bisect, insort, bisect_left, insort_left
input = stdin.readline

def sieve(n):
	prime = [True] * (n + 1)
	p = 2
	prime[0] = False
	prime[1] = False
	for p in range(2, int(n ** 0.5) + 1):
		if prime[p] == True:
			for l1 in range(p * p, n + 1, p):
				prime[l1] = False
	return prime

def simplesieve(n):
	prime = [2]
	mak = [False] * (n + 1)
	for p in range(3, n + 1, 2):
		if mak[p] == False:
			prime.append(p)
			if p * p <= n:
				for l1 in range(p * p, n + 1, 2 * p):
					mak[l1] = True
	return prime

def segementedsieve(low, high):
	primes = simplesieve(int(high ** 0.5))
	prime = [True] * (high - low + 1)
	for i in primes:
		lower = low // i * i
		if lower < low:
			lower += i
		for j in range(lower, high + 1, i):
			if j != i:
				prime[j - low] = False
	ans = []
	for i in range(low, high + 1):
		if prime[i - low]:
			ans.append(i)
	return ans

def isprime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n == 1:
		return False
	for l1 in range(3, int(n ** 0.5) + 1, 2):
		if n % l1 == 0:
			return False
	return True

def binpow(a, b, m):
	r2 = 1
	a = a % m
	while b > 0:
		if b & 1:
			r2 = r2 * a % m
		a = a * a % m
		b >>= 1
	return r2

def lcm(a, b):
	return a // gcd(a, b) * b

def gcdExtended(a, b):
	if b == 0:
		return (a, 1, 0)
	(g, x1, y1) = gcdExtended(b, a % b)
	(x1, y1) = (y1, x1 - a // b * y1)
	return (g, x1, y1)

def binseach(a, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if a[m] <= key:
			l = m
		else:
			r = m
	if a[l] == key:
		return l
	if a[r] == key:
		return r
	return -1

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

def inorder(root):
	(res, stack) = ([], [])
	current = root
	while True:
		while current:
			stack.append(current)
			current = current.left
		if len(stack) == 0:
			return res
		node = stack[-1]
		stack.pop(len(stack) - 1)
		if node.data != None:
			res.append(node.data)
		current = node.right
	return res

def dfs(graph, s, v, ans):
	v[s] = 1
	ans.append(s)
	for i in graph[s]:
		if v[i] == 0:
			dfs(graph, i, v, ans)

def bfs(graph, n, x, dest):
	v = [0] * (1 + n)
	d = [0] * (1 + n)
	d[x] = 0
	v[x] = 1
	q = queue.Queue()
	q.put(x)
	while not q.empty():
		z = q.get()
		for s in graph[z]:
			if v[s] == 0:
				v[s] = 1
				d[s] = d[z] + 1
				q.put(s)
	return d[dest]
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	v = [0] * n
	ans = 0
	for i in range(32, -1, -1):
		c = 0
		for j in range(n):
			if v[j] == 0 and a[j] & 1 << i:
				v[j] = 1
				c += 1
		ans += c * (c - 1) // 2
	print(ans)


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	freq = {}
	for x in arr:
		if x not in freq:
			freq[x] = 0
		freq[x] += 1
	sig = [0] * 31
	for (k, v) in freq.items():
		b = bin(k)
		s = len(b) - 2
		sig[s] += v
	ans = 0
	for i in sig:
		ans += i * (i - 1) // 2
	return ans
for _ in range(int(input())):
	print(main())


from collections import Counter
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = []
	for i in arr:
		brr.append(len(bin(i)[2:]))
	c = Counter(brr)
	s = 0
	for a in list(c.values()):
		s += a * (a - 1) // 2
	print(s)


import math
from collections import defaultdict
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	base = defaultdict(int)
	for k in A:
		base[int(math.floor(math.log2(k))) + 1] += 1
	count = 0
	for v in base.values():
		if v > 1:
			count += (v - 1) * v // 2
	print(count)


import math
tw = lambda n: n * (n - 1) // 2
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = {}
	ans = 0
	for x in a:
		k = int(math.log2(x))
		if k in p:
			p[k] += 1
		else:
			p[k] = 1
	for x in p:
		ans += tw(p[x])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().strip().split(' ')))
	d = {}
	c = 0
	for i in l:
		msb = 0
		while i != 0:
			i = i // 2
			msb = msb + 1
		if msb in d.keys():
			c = c + d[msb]
			d[msb] = d[msb] + 1
		else:
			d[msb] = 1
	print(c)


import math
t = int(input())
while t:
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	c = 0
	M = {}
	for i in range(n):
		f = math.log2(A[i]) // 1
		if f in M:
			M[f] += 1
		else:
			M[f] = 1
	for i in M.values():
		if i != 1:
			c += i * (i - 1) // 2
	print(c)
	t -= 1


for T in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	count1 = 0
	i = 0
	while i < n:
		a = 1
		for j in range(i + 1, n):
			if len(format(l[i], 'b')) == len(format(l[j], 'b')):
				a += 1
			else:
				break
		i += a
		count1 += a * (a - 1) // 2
	print(count1)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		if math.log2(i) // 1 in d:
			d[math.log2(i) // 1] += 1
		else:
			d[math.log2(i) // 1] = 1
	f = 0
	for i in d:
		f += d[i] * (d[i] - 1) // 2
	print(f)


import sys
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
for _ in range(nmbr()):
	n = nmbr()
	a = lst()
	msb = [0] * 35
	for v in a:
		for bp in range(33, -1, -1):
			if v >> bp & 1:
				msb[bp] += 1
				break
	ans = 0
	for v in msb:
		ans += v * (v - 1) // 2
	print(ans)


def findmsb(p):
	msb = 0
	while p != 0:
		p //= 2
		msb += 1
	return msb
for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	msb = [0] * 33
	for i in lis:
		tem = findmsb(i)
		msb[tem] += 1
	pair = 0
	for i in msb:
		if i > 0:
			new = i * (i - 1) // 2
			pair = pair + new
	print(pair)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	l = [len(bin(int(i)).split('b')[-1]) for i in input().split()]
	k = 0
	r = 1
	l = sorted(l)
	for i in range(1, n):
		if l[i] == l[i - 1]:
			k += r
			r += 1
		else:
			r = 1
	print(k)


import sys
from math import sqrt, gcd, factorial, ceil, floor
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	n = I()
	a = L()
	d = [0] * 32
	ans = 0
	for i in a:
		ans += d[len(bin(i)) - 2]
		d[len(bin(i)) - 2] += 1
	print(ans)


from sys import stdin
input = stdin.readline
from math import log, floor
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	num = max(a)
	sm = bin(num).replace('0b', '')
	ml = len(sm)
	b = [0] * ml
	for i in range(n):
		s = bin(a[i]).replace('0b', '')
		s = '0' * (ml - len(s)) + s
		for j in range(ml):
			if s[j] == '1':
				b[j] += 1
				break
	ans = 0
	for i in range(ml):
		ans += b[i] * (b[i] - 1) // 2
	print(ans)


import math
import bisect
power = [0 for i in range(34)]
ans = 1
for i in range(34):
	power[i] = ans - 1
	ans *= 2
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	dp = [[0 for i in range(n + 1)] for j in range(34)]
	bisectele = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		temp = bisect.bisect_left(power, l[i])
		bisectele[i] = temp
		dp[temp][i] += 1
	for i in range(33):
		for j in range(n - 1, -1, -1):
			dp[i][j] += dp[i][j + 1]
	ans = 0
	for i in range(32):
		temp = dp[i][0]
		ans += temp * (temp - 1) // 2
	print(ans)