Read problems statements [Hindi] ,[Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.

Chef is stuck at the following problem. Help him solve it!

Chef has a sequence of integers $A_{1}, A_{2}, \dots, A_{N}$. He should find the number of pairs $(i, j)$ such that $1 ≤ i < j ≤ N$ and the bitwise XOR of $A_{i}$ and $A_{j}$ can be written as a sum of two (not necessarily different) prime numbers with the same parity (both odd or both even).

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$. 
The second line contains $N$ space-seprated integers $A_{1}, A_{2}, \dots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer — the number of valid pairs.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{6}$ for each valid $i$

------  Subtasks ------
Subtask #1 (10 points): $1 ≤ N ≤ 10^{3}$

Subtask #2 (90 points): original constraints

----- Sample Input 1 ------ 
1
5
2 4 8 1 3
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 
Example case 1: The three valid pairs are $(1, 2)$, $(1, 3)$ and $(2, 3)$. For example, $A_{1} \oplus A_{2} = 2 \oplus 4 = 6 = 3+3$.

Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Starter code:

Solutions:
from collections import defaultdict
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	occurances = defaultdict(lambda : 0)
	no = 0
	ne = 0
	ans = 0
	for i in range(N):
		if A[i] % 2 == 0:
			X = 2 ^ A[i]
			cne = ne - occurances[X] - occurances[A[i]]
			ans += cne
			ne += 1
		else:
			X = 2 ^ A[i]
			cno = no - occurances[X] - occurances[A[i]]
			ans += cno
			no += 1
		occurances[A[i]] += 1
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = defaultdict(lambda : 0)
	even = odd = 0
	count = 0
	for i in l:
		d[i] += 1
		if i & 1:
			odd += 1
		else:
			even += 1
	for i in l:
		if i % 2 == 0:
			count = count + even
		else:
			count = count + odd
		if i ^ 2 in d:
			count = count - d[i ^ 2]
		count = count - d[i]
	print(int(count / 2))


t = int(input())
while t > 0:
	n = int(input())
	lst = list(map(int, input().split()))
	lst_dct = {}
	lst_even = [0] * n
	lst_odd = [0] * n
	var_even = 0
	var_odd = 0
	for i in range(n - 1, -1, -1):
		if lst[i] % 2 == 0:
			var_even += 1
		else:
			var_odd += 1
		lst_even[i] = var_even
		lst_odd[i] = var_odd
	lst_even.append(0)
	lst_odd.append(0)
	for i in range(n):
		if lst[i] % 4 == 0:
			if lst[i] in lst_dct:
				lst_dct[lst[i]].append(i)
			elif lst[i] + 2 in lst_dct:
				lst_dct[lst[i] + 2].append(i)
			else:
				lst_dct[lst[i]] = [i]
		elif (lst[i] + 2) % 4 == 0:
			if lst[i] in lst_dct:
				lst_dct[lst[i]].append(i)
			elif lst[i] - 2 in lst_dct:
				lst_dct[lst[i] - 2].append(i)
			else:
				lst_dct[lst[i]] = [i]
		elif (lst[i] + 1) % 4 == 0:
			if lst[i] in lst_dct:
				lst_dct[lst[i]].append(i)
			elif lst[i] - 2 in lst_dct:
				lst_dct[lst[i] - 2].append(i)
			else:
				lst_dct[lst[i]] = [i]
		elif lst[i] in lst_dct:
			lst_dct[lst[i]].append(i)
		elif lst[i] + 2 in lst_dct:
			lst_dct[lst[i] + 2].append(i)
		else:
			lst_dct[lst[i]] = [i]
	total = 0
	for i in lst_dct:
		if i % 2 == 0:
			length = len(lst_dct[i])
			for j in range(length):
				total += lst_even[lst_dct[i][j] + 1] - (length - j - 1)
		else:
			length = len(lst_dct[i])
			for j in range(length):
				total += lst_odd[lst_dct[i][j] + 1] - (length - j - 1)
	print(total)
	t -= 1


def lisin():
	a = list(map(int, input().split()))
	return a
for tastcas in range(int(input())):
	n = int(input())
	a = lisin()
	freq = [0] * 2000000
	odds = evens = ans = 0
	for i in range(n):
		freq[a[i]] += 1
		if a[i] % 2 == 1:
			odds += 1
		else:
			evens += 1
	for i in range(n):
		if a[i] % 2 == 1:
			ans += odds
		else:
			ans += evens
		ans -= freq[a[i]] + freq[a[i] ^ 2]
	print(ans // 2)


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	(ans, odd, even) = (0, 0, 0)
	(f1, f2) = ({}, {})
	for i in range(n):
		x1 = f1.get(l[i], 0) + 1
		f1[l[i] ^ 0] = x1
		x2 = f2.get(l[i], 0) + 1
		f2[l[i]] = x2
		if l[i] % 2:
			odd += 1
		else:
			even += 1
	ans = even * (even - 1) // 2 + odd * (odd - 1) // 2
	for i in f1.values():
		ans -= i * (i - 1) // 2
	exclude = 0
	for i in f2:
		exclude += f2[i] * f2.get(i ^ 2, 0)
	print(ans - exclude // 2)


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time
import bisect
from collections import defaultdict

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def xor_even_pairs_without_zero_two(a):
	n = len(a)
	freq_arr = Counter(a)
	return n * (n - 1) // 2 - sum((i * (i - 1) // 2 for i in freq_arr.values()))

def main():
	for _ in tr():
		n = nl()
		a = ln()
		t = ([], [])
		for i in a:
			t[i & 1].append(i >> 2)
		print(sum(map(xor_even_pairs_without_zero_two, t)))
main()


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time
import bisect
from collections import defaultdict

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def main():
	for _ in tr():
		n = nl()
		a = ln()
		odd_count = 0
		even_count = 0
		freq_arr = defaultdict(int)
		for i in a:
			if i & 1:
				odd_count += 1
			else:
				even_count += 1
			freq_arr[i] += 1
		count = 0
		for i in range(n):
			if a[i] & 1:
				count += odd_count
			else:
				count += even_count
			count -= freq_arr[a[i] ^ 2]
			count -= freq_arr[a[i]]
		print(count >> 1)
main()


T = int(input())
for i in range(T):
	n = int(input())
	A = list(map(int, input().split(' ')))
	odd = []
	even = []
	for item in A:
		if item % 2 == 1:
			odd.append(item)
		else:
			even.append(item)
	odd.sort()
	even.sort()
	counter = 0
	i = 0
	while i < len(odd):
		j = 0
		q = 0
		while i < len(odd) - 1 and odd[i] == odd[i + 1]:
			i = i + 1
			q = q + 1
		while i + j + 1 < len(odd) and odd[i] ^ odd[i + j + 1] == 2:
			j = j + 1
		counter = counter + (q + 1) * (len(odd) - (i + j + 1))
		i = i + 1
	i = 0
	while i < len(even):
		j = 0
		q = 0
		while i < len(even) - 1 and even[i] == even[i + 1]:
			i = i + 1
			q = q + 1
		while i + j + 1 < len(even) and even[i] ^ even[i + j + 1] == 2:
			j = j + 1
		counter = counter + (q + 1) * (len(even) - (i + j + 1))
		i = i + 1
	print(counter)


import sys, math
from collections import Counter
sys.setrecursionlimit(10 ** 5)

def pro(arr):
	n = len(arr)
	e = []
	o = []
	for i in range(n):
		if arr[i] % 2 == 0:
			e.append(arr[i])
		else:
			o.append(arr[i])
	print(helper(e) + helper(o))

def helper(e):
	c = len(e)
	ans = c * (c - 1) // 2
	x = 0
	for i in range(c):
		e[i] = e[i] >> 2
	dic = Counter(e)
	for (i, j) in dic.items():
		x += j * (j - 1) // 2
	return ans - x

def check(arr):
	n = len(arr)
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			x = arr[i] ^ arr[j]
			if i != j and x != 2 and (x % 2 == 0):
				ans += 1
	print(ans)
n = int(input())
for i in range(n):
	n = int(input())
	arr = list(map(int, input().split()))
	pro(arr)


from sys import stdin, stdout
from collections import Counter
input = stdin.readline
t = int(input().strip())

def func(arr, arr_dict):
	ded = 0
	n = len(arr)
	for key in arr_dict:
		value = arr_dict[key]
		if value >= 2:
			ded += (value - 1) * value // 2
	for i in range(n - 1):
		num1 = arr[i]
		num2 = arr[i + 1]
		if num1 ^ num2 == 2:
			ded += arr_dict[num1] * arr_dict[num2]
	return ded
for _ in range(t):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	arr.sort()
	odd = [arr[i] for i in range(n) if arr[i] % 2 != 0]
	even = [arr[i] for i in range(n) if arr[i] % 2 == 0]
	n1 = len(odd)
	n2 = len(even)
	odd_dict = Counter(odd)
	even_dict = Counter(even)
	odd = sorted(set(odd))
	even = sorted(set(even))
	total = (n1 - 1) * n1 // 2 + (n2 - 1) * n2 // 2
	ded = func(odd, odd_dict) + func(even, even_dict)
	ans = total - ded
	print(ans)


def findNum(l):
	e = {}
	even = 0
	odd = 0
	for i in l:
		if i not in e:
			e[i] = 1
		else:
			e[i] = e[i] + 1
		if i % 2 == 0:
			even = even + 1
		else:
			odd = odd + 1
	count = 0
	for i in l:
		if i % 2 == 0:
			count = count + even
		else:
			count = count + odd
		if i ^ 2 in e:
			count = count - e[i ^ 2]
		count = count - e[i]
	print(int(count / 2))
u = int(input())
l = []
while u > 0:
	n = int(input())
	l.append(list(map(int, input().split())))
	u = u - 1
for i in l:
	findNum(i)


def find(li):
	d = {}
	even = 0
	odd = 0
	for i in li:
		if i not in d:
			d[i] = 1
		else:
			d[i] = d[i] + 1
		if i % 2 == 0:
			even = even + 1
		else:
			odd = odd + 1
	count = 0
	for i in li:
		if i % 2 == 0:
			count = count + even
		else:
			count = count + odd
		if i ^ 2 in d:
			count = count - d[i ^ 2]
		count = count - d[i]
	print(int(count / 2))
t = int(input())
li = []
while t > 0:
	n = int(input())
	li.append(list(map(int, input().split())))
	t = t - 1
for i in li:
	find(i)


import math
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split(' ')))
	(k, l) = ({}, {})
	(u, v, c) = (0, 0, 0)
	for i in A:
		j = i >> 2
		if i % 2:
			c += 1
			t = k.get(j, 0)
			u += t
			k[j] = t + 1
		else:
			t = l.get(j, 0)
			v += t
			l[j] = t + 1
	print(c * (c - 1) // 2 + (n - c) * (n - c - 1) // 2 - u - v)


import math
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split(' ')))
	(k, l) = ({}, {})
	(u, v) = (0, 0)
	(x, y) = (0, 0)
	for i in A:
		j = i >> 2
		if i % 2:
			t = k.get(j, 0)
			u += t
			x += 1 if t else 0
			k[j] = t + 1
		else:
			t = l.get(j, 0)
			v += t
			y += 1 if t else 0
			l[j] = t + 1
	(a, b) = (len(k), len(l))
	print((a + x) * (a + x - 1) // 2 + (b + y) * (b + y - 1) // 2 - u - v)


def count_pairs(lst):
	d = create_count_map(lst)
	ans = 0
	for i in d:
		ans += d[i] * (d[i] - 1) // 2
	return ans

def create_count_map(lst):
	result = {}
	for item in lst:
		if item in result:
			result[item] += 1
		else:
			result[item] = 1
	return result

def get_count(lst, x):
	count_map = create_count_map(lst)
	total_pairs = 0
	for item in count_map:
		xor_res = item ^ x
		if xor_res in count_map:
			total_pairs += count_map[xor_res] * count_map[item]
	return total_pairs // 2
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	count = 0
	ar = [i for i in a if i % 2 == 0]
	br = [i for i in a if i % 2 != 0]
	a = len(ar)
	b = len(br)
	c1 = get_count(ar[:], 2)
	c2 = get_count(br[:], 2)
	c3 = count_pairs(ar[:])
	c4 = count_pairs(br[:])
	count = a * (a - 1) // 2 + b * (b - 1) // 2 - c1 - c2 - c3 - c4
	print(count)


from collections import *
import sys
input = sys.stdin.readline
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	f = Counter(a)
	r = 0
	e = 0
	for i in a:
		if i % 2:
			e += 1
	r += e * (e - 1) // 2
	e = n - e
	r += e * (e - 1) // 2
	for i in f.keys():
		q = i // 2
		re = f[i] * (f[i] - 1)
		re = re // 2
		r -= re
		if q % 2 == 1:
			continue
		if i + 2 in f:
			re = f[i] * f[i + 2]
			r -= re
	print(r)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0] * 10000002
	(tnoo, tnoe, noo, noe) = (0, 0, 0, 0)
	b[a[0]] += 1
	for i in range(1, n):
		b[a[i]] += 1
		d = a[i] ^ a[i - 1]
		if d % 2 == 0:
			noe += 1
			noo = noo
		else:
			c = noo
			noo = noe + 1
			noe = c
		tnoo = tnoo + noo
		tnoe = tnoe + noe
		if b[a[i]] > 1:
			tnoe = tnoe - (b[a[i]] - 1)
		br = a[i] - 2
		fr = a[i] + 2
		if b[fr] > 0 and fr ^ a[i] == 2:
			tnoe = tnoe - b[fr]
		if b[br] > 0 and br ^ a[i] == 2:
			tnoe = tnoe - b[br]
	print(tnoe)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	k = []
	for i in l:
		if not i % 2:
			k.append(i)
	d = {}
	for i in k:
		try:
			d[i] += 1
		except:
			d[i] = 1
	m = len(k)
	ans = 0
	x = list(d.keys())
	x.sort()
	for i in x:
		m -= d[i]
		k = m
		try:
			x = d[i + 2]
			if i + 2 ^ i == 2:
				k -= x
		except:
			pass
		ans += d[i] * k
	k = []
	for i in l:
		if i % 2:
			k.append(i)
	d = {}
	for i in k:
		try:
			d[i] += 1
		except:
			d[i] = 1
	m = len(k)
	x = list(d.keys())
	x.sort()
	for i in x:
		m -= d[i]
		k = m
		try:
			x = d[i + 2]
			if i + 2 ^ i == 2:
				k -= x
		except:
			pass
		ans += d[i] * k
	print(ans)


from collections import Counter
t = int(input())
while t > 0:
	n = int(input())
	(odds, evens) = (0, 0)
	a = [int(i) for i in input().split()]
	for i in range(n):
		if a[i] & 1 == 0:
			evens += 1
		else:
			odds += 1
	count = 0
	c = Counter(a)
	for i in range(n - 1):
		if a[i] & 1 == 1:
			odds -= 1
		else:
			evens -= 1
		c[a[i]] -= 1
		if a[i] & 1:
			count += odds - c[a[i]]
		else:
			count += evens - c[a[i]]
		if a[i] & 2 == 2:
			count -= c[a[i] - 2]
		else:
			count -= c[a[i] + 2]
	print(count)
	t -= 1


for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	o = []
	e = []
	os = set()
	es = set()
	docc = {}
	dtwo = {}
	i = 0
	while i < len(l):
		if l[i] in docc:
			y = docc[l[i]]
			docc[l[i]] = y + 1
		else:
			docc[l[i]] = 1
		if l[i] % 2 == 0:
			es.add(l[i])
			e.append(l[i])
		else:
			os.add(l[i])
			o.append(l[i])
		i = i + 1
	os = list(os)
	es = list(es)
	topair = len(o) ** 2 - len(o)
	tepair = len(e) ** 2 - len(e)
	i = 0
	while i < len(os):
		two = os[i] ^ 2
		dtwo[os[i]] = two
		i = i + 1
	i = 0
	while i < len(es):
		two = es[i] ^ 2
		dtwo[es[i]] = two
		i = i + 1
	remove = 0
	i = 0
	while i < len(os):
		fz = docc[os[i]]
		mktwo = dtwo[os[i]]
		zero = fz * (fz - 1)
		if mktwo in docc:
			valmk = docc[mktwo]
		else:
			valmk = 0
		retwo = valmk * fz
		remove = remove + zero + retwo
		i = i + 1
	i = 0
	while i < len(es):
		fz = docc[es[i]]
		mktwo = dtwo[es[i]]
		zero = fz * (fz - 1)
		if mktwo in docc:
			valmk = docc[mktwo]
		else:
			valmk = 0
		retwo = valmk * fz
		remove = remove + zero + retwo
		i = i + 1
	result = topair + tepair - remove
	print(result // 2)


t = int(input())
while t > 0:
	n = int(input())
	a = [int(x) for x in input().split()]
	even = []
	odd = []
	d = {}
	rpt = {}
	for x in a:
		if x % 2 == 0:
			even.append(x)
		else:
			odd.append(x)
		if x in rpt:
			rpt[x] += 1
		else:
			rpt[x] = 1
	for x in even:
		temp = x ^ 2
		d[temp] = 0
	for x in odd:
		temp = x ^ 2
		d[temp] = 0
	for x in even:
		if x in d:
			d[x] += 1
	for x in odd:
		if x in d:
			d[x] += 1
	ett = len(even) * (len(even) - 1) // 2
	ott = len(odd) * (len(odd) - 1) // 2
	tt = ott + ett
	temp = 0
	for x in rpt.values():
		temp += x * (x - 1) // 2
	temp1 = 0
	for x in d.keys():
		if d[x] != 0:
			temp1 += d[x] * d[x ^ 2]
	tt = tt - temp
	tt -= temp1 // 2
	print(tt)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = [0] * int(1000000.0 + 10)
	even = 0
	odd = 0
	for i in range(n):
		if l[i] % 2 != 0:
			odd += 1
		else:
			even += 1
		d[l[i]] += 1
	ans = 0
	for i in range(n):
		if l[i] % 2 != 0:
			ans += odd
		else:
			ans += even
		ans -= d[l[i]]
		ans -= d[2 ^ l[i]]
	print(ans // 2)


def res():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		noe = 0
		nod = n
		x = {}
		y = {}
		for i in range(250001):
			x[i] = 0
			y[i] = 0
		ans = 0
		for i in range(n):
			m = a[i] // 4
			if a[i] % 2 == 0:
				noe = noe + 1
				x[m] = x[m] + 1
			else:
				y[m] = y[m] + 1
		nod = nod - noe
		ans = noe * (noe - 1) // 2 + nod * (nod - 1) // 2
		for i in x:
			ans = ans - (x[i] * (x[i] - 1) // 2 + y[i] * (y[i] - 1) // 2)
		print(ans)
res()


from collections import Counter
t = int(input())
for o in range(t):
	n = int(input())
	final = 0
	lst = list(map(int, input().split()))
	frequent = dict(Counter(lst))
	(ev, oddnumber) = (0, 0)
	k = 0
	for i in lst:
		if i % 2 == 0:
			ev += 1
		else:
			oddnumber += 1
		if i ^ 2 in frequent.keys():
			k = k + frequent[i ^ 2] + frequent[i]
		else:
			k = k + frequent[i]
	final = oddnumber * oddnumber + ev * ev - k
	print(final >> 1)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	l = list(map(int, input().split()))
	fr = dict(Counter(l))
	(even, odd) = (0, 0)
	k = 0
	for i in l:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
		if i ^ 2 in fr.keys():
			k = k + fr[i ^ 2] + fr[i]
		else:
			k = k + fr[i]
	ans = odd * odd + even * even - k
	print(ans >> 1)


t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	l = list(map(int, input().split()))
	fr = [0] * 1100001
	for i in range(len(l)):
		fr[l[i]] += 1
	(even, odd) = (0, 0)
	k = 0
	for i in l:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
		k = k + fr[i ^ 2] + fr[i]
	ans = odd * odd + even * even - k
	print(ans >> 1)


def calc_num_of_pairs_in_even_list(even_nums_list):
	count_of_pairs = 0
	even_nums_list.sort()
	even_nums_freq_list = []
	i = 0
	j = 0
	while i < len(even_nums_list):
		even_nums_freq_list.append([even_nums_list[i], 1])
		i += 1
		while i < len(even_nums_list) and even_nums_list[i] == even_nums_freq_list[j][0]:
			even_nums_freq_list[j][1] += 1
			i += 1
		j += 1
	length = len(even_nums_freq_list)
	suffix_freq_sum = [None for _ in range(length)]
	suffix_freq_sum[length - 1] = even_nums_freq_list[length - 1][1]
	for i in reversed(range(length - 1)):
		suffix_freq_sum[i] = even_nums_freq_list[i][1] + suffix_freq_sum[i + 1]
	j = 0
	while j < length - 1:
		num = even_nums_freq_list[j][0]
		freq = even_nums_freq_list[j][1]
		if num % 4 == 2:
			count_of_pairs += freq * suffix_freq_sum[j + 1]
		elif even_nums_freq_list[j + 1][0] == num + 2:
			if j + 2 < length:
				count_of_pairs += freq * suffix_freq_sum[j + 2]
		else:
			count_of_pairs += freq * suffix_freq_sum[j + 1]
		j += 1
	return count_of_pairs

def calc_num_of_pairs_in_odd_list(odd_nums_list):
	count_of_pairs = 0
	odd_nums_list.sort()
	odd_nums_freq_list = []
	i = 0
	j = 0
	while i < len(odd_nums_list):
		odd_nums_freq_list.append([odd_nums_list[i], 1])
		i += 1
		while i < len(odd_nums_list) and odd_nums_list[i] == odd_nums_freq_list[j][0]:
			odd_nums_freq_list[j][1] += 1
			i += 1
		j += 1
	length = len(odd_nums_freq_list)
	suffix_freq_sum = [None for _ in range(length)]
	suffix_freq_sum[length - 1] = odd_nums_freq_list[length - 1][1]
	for i in reversed(range(length - 1)):
		suffix_freq_sum[i] = odd_nums_freq_list[i][1] + suffix_freq_sum[i + 1]
	j = 0
	while j < length - 1:
		num = odd_nums_freq_list[j][0]
		freq = odd_nums_freq_list[j][1]
		if num % 4 == 3:
			count_of_pairs += freq * suffix_freq_sum[j + 1]
		elif odd_nums_freq_list[j + 1][0] == num + 2:
			if j + 2 < length:
				count_of_pairs += freq * suffix_freq_sum[j + 2]
		else:
			count_of_pairs += freq * suffix_freq_sum[j + 1]
		j += 1
	return count_of_pairs
T = int(input())
while T:
	N = int(input())
	A = list(map(int, input().split()))
	even_nums_list = [val for val in A if val % 2 == 0]
	odd_nums_list = [val for val in A if val % 2 == 1]
	count_of_pairs = 0
	if len(even_nums_list) >= 2:
		count_of_pairs += calc_num_of_pairs_in_even_list(even_nums_list)
	if len(odd_nums_list) >= 2:
		count_of_pairs += calc_num_of_pairs_in_odd_list(odd_nums_list)
	print(count_of_pairs)
	T -= 1


T = int(input())
for loop in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	cnt = [0] * (10 ** 6 + 1)
	for a in A:
		cnt[a] += 1
	odd = sum((a % 2 == 1 for a in A))
	even = sum((a % 2 == 0 for a in A))
	ans = odd * (odd - 1) // 2 + even * (even - 1) // 2
	for i in range(1, 10 ** 6 + 1):
		ans -= cnt[i] * (cnt[i] - 1) // 2
		j = i ^ 2
		if i < j and j <= 10 ** 6:
			ans -= cnt[i] * cnt[j]
	print(ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	rr = []
	t = I()

	def f(d):
		r = 0
		c = sum(d.values())
		for (k, v) in d.items():
			cc = c - v
			cc -= d[k ^ 2]
			r += v * cc
		return r // 2
	for _ in range(t):
		n = I()
		a = LI()
		b = [c for c in a if c % 2 == 0]
		d = [c for c in a if c % 2 == 1]
		bc = collections.Counter(b)
		dc = collections.Counter(d)
		r = f(bc)
		r += f(dc)
		rr.append(r)
	return '\n'.join(map(str, rr))
print(main())


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	oc = sum((i % 2 for i in l))
	ec = sum((i % 2 == 0 for i in l))
	cnt = 0
	from collections import Counter
	c = Counter(l)
	for i in range(n):
		if l[i] % 2 == 0:
			cnt += ec - c[l[i]] - c[l[i] ^ 2]
		else:
			cnt += oc - c[l[i]] - c[l[i] ^ 2]
	print(cnt // 2)


import collections
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = collections.Counter(a)
	(o, e, res) = (0, 0, 0)
	for i in range(n):
		if a[i] & 1:
			o += 1
		else:
			e += 1
	for i in range(n):
		if a[i] & 1:
			res += o
		else:
			res += e
		res -= cnt[a[i] ^ 2]
		res -= cnt[a[i]]
	print(res // 2)


from sys import stdin
from collections import Counter

class pair(object):

	def __init__(self, one=None, two=None):
		self.one = one
		self.two = two
for _ in range(int(stdin.readline())):
	eventotal = 0
	eve = 0
	oddtotal = 0
	od = 0
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	a = dict(Counter(a))
	a = dict([(key, value) for (key, value) in sorted(a.items())])
	even = []
	odd = []
	for (k, v) in a.items():
		if k % 2 == 0:
			even.append(pair(k, v))
		else:
			odd.append(pair(k, v))
	for i in range(even.__len__()):
		if i < even.__len__() - 1:
			if even[i].one ^ even[i + 1].one == 2:
				eve += even[i].two * even[i + 1].two
		eventotal += even[i].two
		eve += even[i].two * (even[i].two - 1) / 2
	for i in range(odd.__len__()):
		if i < odd.__len__() - 1:
			if odd[i].one ^ odd[i + 1].one == 2:
				od += odd[i].two * odd[i + 1].two
		oddtotal += odd[i].two
		od += odd[i].two * (odd[i].two - 1) / 2
	eveans = eventotal * (eventotal - 1) / 2
	eveans -= eve
	oddans = oddtotal * (oddtotal - 1) / 2
	oddans -= od
	print(int(eveans + oddans))


import collections
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = collections.Counter(a)
	(odd, even, ans) = (0, 0, 0)
	for i in range(n):
		if a[i] & 1:
			odd += 1
		else:
			even += 1
	for i in range(n):
		if a[i] & 1:
			ans += odd
		else:
			ans += even
		ans -= cnt[a[i] ^ 2]
		ans -= cnt[a[i]]
	print(int(ans / 2))


t = int(input())
for xx in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(even, odd, pair) = (0, 0, 0)
	a = [0 for i in range(10000001)]
	for i in arr:
		a[i] += 1
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	pair = even * (even - 1) // 2 + odd * (odd - 1) // 2
	for i in arr:
		if a[i] == 0:
			pass
		pair -= a[i] * (a[i] - 1) // 2
		b = i ^ 2
		pair -= a[i] * a[b]
		a[i] = 0
	print(pair)


for __ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	Af = dict()
	o = 0
	e = 0
	for a in A:
		if a % 2 == 0:
			e += 1
		else:
			o += 1
		if a in Af.keys():
			Af[a] += 1
		else:
			Af[a] = 1
	t = 0
	r = 0
	for u in Af.keys():
		if Af[u] > 1:
			t += Af[u] * (Af[u] - 1) // 2
		if u + 2 in Af.keys() and u ^ u + 2 == 2:
			t += Af[u] * Af[u + 2]
	r = (e * (e - 1) + o * (o - 1)) // 2
	r = r - t
	print(r)


def nc2(n):
	return n * (n - 1) // 2
t = int(input())
for case in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		if a[0] > 2 and a[0] % 2 == 0:
			print(1)
		else:
			print(0)
		continue
	c = [0] * 1000001
	(e, o, m, j) = [0, 0, 0, 0]
	for i in a:
		c[i] += 1
	for i in range(0, 1000001):
		if c[i] > 0:
			if i % 2 == 0:
				e += c[i]
			else:
				o += c[i]
		if c[i] > 1:
			m += nc2(c[i])
		if i ^ 2 < 1000001 and i ^ 2 >= i:
			j = j + c[i] * c[i ^ 2]
	res = nc2(e) + nc2(o) - m - j
	print(res)


def ip():
	return int(input())

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

def sar():
	return list(ipp())

def pars(a):
	print(' '.join(list(map(str, a))))
	print('\r')

def parl(a):
	print('\r'.join(list(map(str, a))))
	print('\r')
T = 1
T = int(input().strip())
for _ in range(T):
	n = ip()
	a = sar()
	odd = 0
	even = 0
	mp = {}
	for i in a:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
		if i in mp:
			mp[i] += 1
		else:
			mp[i] = 1
	ans = even * (even - 1) // 2 + odd * (odd - 1) // 2
	ex = 0
	for i in mp:
		ex += mp[i] * (mp[i] - 1) // 2
	for i in range(1, 1000001):
		if i ^ i + 2 == 2:
			if i in mp and i + 2 in mp:
				ex += mp[i] * mp[i + 2]
	print(ans - ex)


t = int(input())
while t > 0:
	n = int(input())
	(a, b) = ([], [])
	for i in range(1000005):
		b.append(0)
	a = [int(i) for i in input().split()]
	(odd, even, diff) = (0, 0, 0)
	for j in range(n):
		b[a[j]] += 1
		if a[j] % 2 == 0:
			even += 1
		else:
			odd += 1
	ans = (odd * odd + even * even - (odd + even)) // 2
	for k in range(n):
		xor = a[k] ^ 2
		diff = diff + b[xor] + b[a[k]] - 1
	print(ans - diff // 2)
	t -= 1


from collections import Counter

def f(a):
	n = len(a)
	d = Counter(a)
	c = lambda x: x * (x - 1) // 2
	return c(n) - sum(map(c, d.values()))
t = int(input())
for _ in range(t):
	input()
	a = map(int, input().split())
	l = ([], [])
	for x in a:
		l[x & 1].append(x >> 2)
	print(sum(map(f, l)))


t = int(input())
for i in range(t):
	k = int(input())
	l = list(map(int, input().split()))
	even = {}
	odd = {}
	(n, m) = (0, 0)
	for e in l:
		if e % 2 == 0:
			n += 1
			even[e] = even.get(e, 0) + 1
		else:
			m += 1
			odd[e] = odd.get(e, 0) + 1
	total1 = n * (n - 1) // 2
	for key in sorted(even.keys()):
		a = key + 2
		count = 0
		if a ^ key < 4 and a in even.keys():
			count = even[key] * even[a]
		count += even[key] * (even[key] - 1) // 2
		total1 = total1 - count
	total2 = m * (m - 1) // 2
	for key in sorted(odd.keys()):
		a = key + 2
		count = 0
		if a ^ key < 4 and a in odd.keys():
			count = odd[key] * odd[a]
		count += odd[key] * (odd[key] - 1) // 2
		total1 = total1 - count
	print(total1 + total2)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	e = []
	ec = 0
	oc = 0
	o = []
	de = defaultdict(int)
	doo = defaultdict(int)
	for i in range(n):
		if l[i] % 2 == 0:
			e.append(l[i])
			ec += 1
			de[l[i]] += 1
		else:
			o.append(l[i])
			oc += 1
			doo[l[i]] += 1
	c = ec * (ec - 1) / 2 + oc * (oc - 1) / 2
	t = 0
	for i in range(n):
		if l[i] % 2 == 0:
			if l[i] ^ 2 in de:
				t += de[l[i] ^ 2]
			if l[i] ^ 0 in de:
				t += de[l[i] ^ 0] - 1
		else:
			if l[i] ^ 2 in doo:
				t += doo[l[i] ^ 2]
			if l[i] ^ 0 in doo:
				t += doo[l[i] ^ 0] - 1
	print(int(c - t // 2))


t = int(input())
for _ in range(t):
	k = int(input())
	lst = list(map(int, input().split()))
	lsto = []
	lste = []
	dicto = dict()
	dicte = dict()
	o = 0
	e = 0
	for i in lst:
		if i % 2 == 0:
			if i in dicte:
				dicte[i] += 1
			else:
				lste.append(i)
				dicte[i] = 1
			e += 1
		else:
			if i in dicto:
				dicto[i] += 1
			else:
				lsto.append(i)
				dicto[i] = 1
			o += 1
	lsto.sort()
	lste.sort()
	c = 0
	for i in lste:
		if i % 4 == 0 and i + 2 in dicte:
			c += (e - dicte[i] - dicte[i + 2]) * dicte[i]
		else:
			c += (e - dicte[i]) * dicte[i]
		e -= dicte[i]
	for i in lsto:
		if (i - 1) % 4 == 0 and i + 2 in dicto:
			c += (o - dicto[i] - dicto[i + 2]) * dicto[i]
		else:
			c += (o - dicto[i]) * dicto[i]
		o -= dicto[i]
	print(c)


def check(s):
	if s == 4:
		return 1
	if s < 5:
		return 0
	if s % 6 == 0 or s % 6 == 2 or s % 6 == 4:
		return 1
	return 0
t = input()
t = int(t)
for _ in range(t):
	temp = input()
	temp = int(temp)
	lst = [int(i) for i in input().split()]
	ev = []
	odd = []
	dict_ev = {}
	dict_odd = {}
	for i in lst:
		if i % 2 == 0:
			if i not in dict_ev:
				dict_ev[i] = 0
				ev.append(i)
			dict_ev[i] += 1
		else:
			if i not in dict_odd:
				dict_odd[i] = 0
				odd.append(i)
			dict_odd[i] += 1
	ct = 0
	ev.sort()
	odd.sort()
	n1 = len(ev)
	n2 = len(odd)
	t1 = [dict_ev[ev[n1 - 1]] for i in range(n1)]
	t2 = [dict_odd[odd[n2 - 1]] for i in range(n2)]
	for i in range(n1 - 2, -1, -1):
		t1[i] = dict_ev[ev[i]] + t1[i + 1]
	for i in range(n2 - 2, -1, -1):
		t2[i] = dict_odd[odd[i]] + t2[i + 1]
	for i in range(n1 - 1):
		if check(ev[i] ^ ev[i + 1]) == 1:
			ct += dict_ev[ev[i]] * t1[i + 1]
		elif i + 2 < n1:
			ct += dict_ev[ev[i]] * t1[i + 2]
	for i in range(n2 - 1):
		if check(odd[i] ^ odd[i + 1]) == 1:
			ct += dict_odd[odd[i]] * t2[i + 1]
		elif i + 2 < n2:
			ct += dict_odd[odd[i]] * t2[i + 2]
	print('{}\n'.format(ct))


for x in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	o = 0
	e = 0
	A = {}
	for val in a:
		if val % 2 == 0:
			e += 1
		else:
			o += 1
		if val in A.keys():
			A[val] += 1
		else:
			A[val] = 1
	RES = 0
	Temp = 0
	for val in A.keys():
		Temp += int(A[val] * (A[val] - 1) / 2)
		if val + 2 in A.keys() and val ^ val + 2 == 2:
			Temp += A[val] * A[val + 2]
	Res = int((e * (e - 1) + o * (o - 1)) / 2)
	Res -= Temp
	print(Res)


t = int(input())
for a in range(t):
	n = int(input())
	f = list(map(int, input().split()))
	(even, odd, leneven, lenodd) = ([], [], 0, 0)
	for y in f:
		if y % 2 == 0:
			even.append(y)
		else:
			odd.append(y)
	even.sort()
	odd.sort()
	ans = 0
	lenodd = len(odd)
	leneven = len(even)
	if leneven > 1:
		(feven, evenc, evenr, var) = ([even[0]], [leneven], [1], 1)
		for i in range(1, leneven):
			if even[i] != even[i - 1]:
				feven.append(even[i])
				evenc.append(leneven - i)
				evenr.append(1)
				var += 1
			else:
				evenr[-1] += 1
		for i in range(var - 1):
			if feven[i] ^ feven[i + 1] > 2:
				ans += evenc[i + 1] * evenr[i]
			elif i + 2 < var:
				ans += evenc[i + 2] * evenr[i]
	if lenodd > 1:
		(fodd, oddc, oddr, var) = ([odd[0]], [lenodd], [1], 1)
		for i in range(1, lenodd):
			if odd[i] != odd[i - 1]:
				fodd.append(odd[i])
				oddc.append(lenodd - i)
				oddr.append(1)
				var += 1
			else:
				oddr[-1] += 1
		for i in range(var - 1):
			if fodd[i] ^ fodd[i + 1] > 2:
				ans += oddc[i + 1] * oddr[i]
			elif i + 2 < var:
				ans += oddc[i + 2] * oddr[i]
	print(ans)


import itertools
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = [int(temp) for temp in input().strip().split()]
	eve = []
	odd = []
	for temp in a:
		eve.append(temp) if temp % 2 == 0 else odd.append(temp)
	(el, ol) = (len(eve), len(odd))
	(ecount, ocount) = (Counter(eve), Counter(odd))
	count = el * (el - 1) // 2 + ol * (ol - 1) // 2
	(eve, odd) = (list(set(eve)), list(set(odd)))
	eve.sort()
	odd.sort()
	(el, ol) = (len(eve), len(odd))
	for i in range(el):
		count = count - ecount[eve[i]] * (ecount[eve[i]] - 1) // 2
		if i < el - 1:
			xor = eve[i] ^ eve[i + 1]
			if xor == 2:
				count = count - ecount[eve[i]] * ecount[eve[i + 1]]
	for i in range(ol):
		count = count - ocount[odd[i]] * (ocount[odd[i]] - 1) // 2
		if i < ol - 1:
			xor = odd[i] ^ odd[i + 1]
			if xor == 2:
				count = count - ocount[odd[i]] * ocount[odd[i + 1]]
	print(count)


cases = int(input())
while cases > 0:
	n = int(input())
	(a, b) = ([], [])
	for i in range(1000005):
		b.append(0)
	a = [int(i) for i in input().split()]
	(o, e) = (0, 0)
	for j in range(n):
		b[a[j]] += 1
		if a[j] % 2 == 1:
			o += 1
		else:
			e += 1
	count = o * o + e * e - (o + e)
	for x in range(n):
		key = 2 ^ a[x]
		diff = b[a[x]] + b[key] - 1
		count = count - diff
	print(count // 2)
	cases -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	x = [int(i) for i in input().split()]
	d = {}
	(e, o) = (0, 0)
	for i in x:
		if d.get(i):
			d[i] += 1
		else:
			d[i] = 1
		if i % 2 == 0:
			e += 1
		else:
			o += 1
	tp = e * (e - 1) // 2 + o * (o - 1) // 2
	ip = 0
	for i in d:
		if d[i] > 1:
			ip += d[i] * (d[i] - 1) // 2
	for i in d:
		t = i ^ 2
		if d.get(t) and d[t] > 0:
			ip += d[t] * d[i]
			(d[t], d[i]) = (0, 0)
	print(tp - ip)


def perm(n):
	return n * (n - 1) // 2
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()[:n]))
	even = []
	odd = []
	for i in a:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	even.sort()
	odd.sort()
	coun = 0
	res = 0
	le = len(even)
	lo = len(odd)
	hal = 1
	peh = 1
	flag = False
	for i in range(le - 1):
		if even[i] == even[i + 1]:
			hal += 1
		elif even[i] ^ even[i + 1] < 4:
			coun += perm(hal)
			if flag:
				coun += peh * hal
			else:
				flag = True
			peh = hal
			hal = 1
		elif even[i] ^ even[i + 1] >= 4:
			coun += perm(hal)
			if flag:
				coun += peh * hal
				flag = 0
			peh = hal
			hal = 1
	if flag:
		coun += perm(hal)
		coun += peh * hal
		flag = False
	else:
		coun += perm(hal)
	peh = 1
	hal = 1
	flag = False
	for i in range(lo - 1):
		if odd[i] == odd[i + 1]:
			hal += 1
		elif odd[i] ^ odd[i + 1] < 4:
			coun += perm(hal)
			if flag:
				coun += peh * hal
			else:
				flag = True
			peh = hal
			hal = 1
		elif odd[i] ^ odd[i + 1] >= 4:
			coun += perm(hal)
			if flag:
				coun += peh * hal
				flag = False
			peh = hal
			hal = 1
	if flag:
		coun += perm(hal)
		coun += peh * hal
		flag = False
	else:
		coun += perm(hal)
	res += perm(le)
	res += perm(lo)
	res -= coun
	print(res)


from random import randint

def calculate(h):
	if h == 1 or h == 0:
		return 0
	if h == 2:
		return 1
	return h - 1 + calculate(h - 1)
t = int(input())
for i in range(t):
	n = int(input())
	list1 = list(map(int, input().strip().split(' ')))
	list2 = []
	list3 = []
	for j in list1:
		if j % 2 == 0:
			list2.append(j)
		else:
			list3.append(j)
	result = (len(list2) - 1) * len(list2) // 2 + (len(list3) - 1) * len(list3) // 2
	list2.sort()
	list3.sort()
	dict1 = {}
	dict2 = {}
	for j in list2:
		if j in dict1:
			dict1[j] = dict1[j] + 1
		else:
			dict1[j] = 1
	for j in list3:
		if j in dict2:
			dict2[j] = dict2[j] + 1
		else:
			dict2[j] = 1
	list2 = list(set(list2))
	list2.sort()
	for j in range(len(list2)):
		result = result - (dict1[list2[j]] - 1) * dict1[list2[j]] // 2
		if j <= len(list2) - 2:
			x = list2[j] ^ list2[j + 1]
			if x == 2:
				result = result - dict1[list2[j]] * dict1[list2[j + 1]]
	list3 = list(set(list3))
	list3.sort()
	for j in range(len(list3)):
		result = result - (dict2[list3[j]] - 1) * dict2[list3[j]] // 2
		if j <= len(list3) - 2:
			x = list3[j] ^ list3[j + 1]
			if x == 2:
				result = result - dict2[list3[j]] * dict2[list3[j + 1]]
	print(result)


t = int(input())
for i in range(t):
	n = int(input())
	A = [int(j) for j in input().split()]
	a = 0
	b = 0
	B = []
	C = []
	for j in range(n):
		if A[j] % 2 == 0:
			a += 1
			B.append(A[j])
		else:
			b += 1
			C.append(A[j])
	B.sort()
	C.sort()
	p = 0
	k = 0
	while k < a - 1:
		pk = B[k] ^ B[k + 1]
		if pk == 2 or pk == 0:
			p += 1
			j = k + 2
			bk = 0
			while j < a and B[j] - B[k] <= 2:
				pk = B[k] ^ B[j]
				if pk == 0 or pk == 2:
					p += 1
					bk += 1
				else:
					break
				j += 1
			pk = B[k] ^ B[k + 1]
			while pk == 0 and k < a - 2:
				k += 1
				p += bk
				bk -= 1
				pk = B[k] ^ B[k + 1]
		k += 1
	k = 0
	while k < b - 1:
		pk = C[k] ^ C[k + 1]
		if pk == 2 or pk == 0:
			p += 1
			j = k + 2
			bk = 0
			while j < b and C[j] - C[k] <= 2:
				pk = C[k] ^ C[j]
				if pk == 0 or pk == 2:
					p += 1
					bk += 1
				else:
					break
				j += 1
		pk = C[k] ^ C[k + 1]
		while pk == 0 and k < b - 2:
			k += 1
			p += bk
			bk -= 1
			pk = C[k] ^ C[k + 1]
		k += 1
	c = (a * (a - 1) + b * (b - 1)) // 2 - p
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	even = {}
	odd = {}
	even_count = 0
	odd_count = 0
	for elem in l:
		if elem % 2 == 0:
			even_count += 1
			even[elem] = even.get(elem, 0) + 1
		else:
			odd_count += 1
			odd[elem] = odd.get(elem, 0) + 1
	even_total = even_count * (even_count - 1) // 2
	for key in sorted(even.keys()):
		x = key + 2
		count = 0
		if x ^ key < 4 and x in even.keys():
			count = even[x] * even[key]
		count += even[key] * (even[key] - 1) // 2
		even_total = even_total - count
	odd_total = odd_count * (odd_count - 1) // 2
	for key in sorted(odd.keys()):
		x = key + 2
		count = 0
		if x ^ key < 4 and x in odd.keys():
			count = odd[x] * odd[key]
		count += odd[key] * (odd[key] - 1) // 2
		odd_total = odd_total - count
	print(odd_total + even_total)


import math
from collections import *

def getoddeven(arr):
	O = []
	E = []
	for v in arr:
		if v & 1:
			O.append(v)
		else:
			E.append(v)
	return (O, E)

def getoddoth(arr):
	pairs = 0
	m = 0
	h = defaultdict(int)
	for v in arr:
		h[v] += 1
	for (v, no) in list(h.items()):
		m += (no * no - no) // 2
		if v // 2 % 2 == 0 and h[v + 2]:
			pairs += h[v] * h[v + 2]
	return pairs + m

def getevenoth(arr):
	pairs = 0
	m = 0
	h = defaultdict(int)
	for v in arr:
		h[v] += 1
	for (v, no) in list(h.items()):
		m += (no * no - no) // 2
		if v // 2 % 2 == 0 and h[v + 2]:
			pairs += h[v] * h[v + 2]
	return pairs + m

def isxor2(a, b):
	if a // 2 % 2 == 0 and b == a + 2:
		return True
	if b // 2 % 2 == 0 and a == b + 2:
		return True
	return False
t = int(input())
for _ in range(t):
	input()
	arr = [int(i) for i in input().split()]
	(O, E) = getoddeven(arr)
	p1 = getoddoth(O)
	p2 = getevenoth(E)
	o = len(O)
	e = len(E)
	ans = (o * o - o) // 2 + (e * e - e) // 2 - (p1 + p2)
	print(ans)


from functools import reduce
from math import *
import operator as op
from collections import defaultdict
fq = defaultdict(int)

def ncr(n, r):
	if n < r:
		return 0
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
T = int(input())
for i in range(T):
	n = int(input())
	x = [int(x) for x in input().split()]
	even = 0
	odd = 0
	special1 = 1.5
	special2 = 1.5
	count = 0
	x.sort()
	l = 1
	curr = x[0]
	cp = 0
	for j in range(len(x)):
		i = x[j]
		if curr == i and j != 0:
			l = l + 1
		if curr != i or j == n - 1:
			cp = cp - l * (l - 1) // 2
			fq[curr] = l
			if j == n - 1 and curr != i:
				fq[i] = 1
			curr = i
			l = 1
	for j in range(len(x)):
		i = x[j]
		if i % 2 == 0:
			even = even + 1
		else:
			odd = odd + 1
		if i % 4 == 1:
			special1 = i
		elif i == special1 + 2:
			special1 = 0.5
			count = count - fq[i] * fq[i - 2]
		if i % 4 == 0:
			special2 = i
		elif i == special2 + 2:
			special2 = 0.5
			count = count - fq[i] * fq[i - 2]
	print(ncr(even, 2) + ncr(odd, 2) + count + cp)


t = int(input())
for case in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	(even, odd) = ([0] * 250001, [0] * 250001)
	(n1, n2) = (0, 0)
	for i in range(n):
		if arr[i] % 2 == 0:
			n1 += 1
			x = arr[i] // 4
			even[x] += 1
		else:
			n2 += 1
			y = arr[i] // 4
			odd[y] += 1
	count = n1 * (n1 - 1) // 2 + n2 * (n2 - 1) // 2
	c = 0
	for i in range(250001):
		c += even[i] * (even[i] - 1) // 2 + odd[i] * (odd[i] - 1) // 2
	print(count - c)


from collections import defaultdict
t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	even = 0
	odd = 0
	for i in a:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	d = defaultdict(int)
	for i in a:
		d[i] += 1
	x = 0
	y = 0
	for i in a:
		x += d[i ^ 2]
	for i in a:
		y += d[i ^ 0]
	print(int(even * (even - 1) / 2 + odd * (odd - 1) / 2 - x / 2 - (y - n) / 2))


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	D = {}
	(l1, l2) = (0, 0)
	for i in range(len(A)):
		if A[i] in D:
			D[A[i]] += 1
		else:
			D[A[i]] = 1
	sum_c = 0
	L = list(D.keys())
	for i in range(len(L)):
		res = L[i] ^ 2
		try:
			sum_c = sum_c + D.get(L[i]) * D.get(res)
		except:
			pass
		sum_c = sum_c + D.get(L[i]) * (D.get(L[i]) - 1) // 2
		if L[i] % 2 == 0:
			l1 = l1 + D.get(L[i])
		else:
			l2 = l2 + D.get(L[i])
		del D[L[i]]
	e = l1 * (l1 - 1) // 2
	o = l2 * (l2 - 1) // 2
	print(e + o - sum_c)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [0] * 1000001
	for j in a:
		b[j] += 1
	even = []
	odd = []
	count = 0
	c = 0
	r = 0
	x = 0
	d = 0
	e = 0
	for j in range(1000001):
		if b[j] > 0:
			if j % 2 == 0:
				even.append(j)
				count += 1
			else:
				odd.append(j)
				c += 1
	if count > 0:
		for j in range(1, count):
			if even[j] ^ even[j - 1] == 2:
				x += b[even[j]] * b[even[j - 1]]
			p = b[even[j]]
			d = d + p
			r += int(p * (p - 1) / 2)
		d += b[even[0]]
		r += int(b[even[0]] * (b[even[0]] - 1) / 2)
	if c > 0:
		for j in range(1, c):
			if odd[j] ^ odd[j - 1] == 2:
				x += b[odd[j]] * b[odd[j - 1]]
			q = b[odd[j]]
			e = e + q
			r += int(q * (q - 1) / 2)
		e += b[odd[0]]
		r += int(b[odd[0]] * (b[odd[0]] - 1) / 2)
	print(int(d * (d - 1) / 2 + e * (e - 1) / 2 - r - x))


def pcount(l, x):
	r = 0
	d = {}
	for i in l:
		c = x ^ i
		if c in d:
			r += d[c]
		if i not in d:
			d[i] = 0
		d[i] += 1
	return r
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	y = 0
	(e, o) = (0, 0)
	x = pcount(l, 0)
	z = pcount(l, 2)
	for i in l:
		if i % 2 == 0:
			e += 1
		else:
			o += 1
	e = e * (e - 1) // 2
	o = o * (o - 1) // 2
	ans = e + o - x - z
	print(ans)