You are given an array A of size N and an integer X. 

Find the count of all the pairs (i,j) such that ((A_{i}  \oplus  A_{j}) \& X) = 0. Here \oplus and \& denote [bitwise XOR] and [bitwise AND] operations respectively..

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

- 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 size of the array.
- The second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} - the elements of the array.
- The third line of each test case contains a single integer X.

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

For each test case, print a single line containing one integer ― the total number of pairs satisfying the condition.

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

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i}, X ≤ 10^{9}$

----- Sample Input 1 ------ 
2
4
1 2 3 1
1
3
0 0 0
21
----- Sample Output 1 ------ 
10
9
----- explanation 1 ------ 
Test case $1$: There are $10$ pairs of $(i,j)$ $(1≤ i,j ≤ N)$ satisfying the condition. These pairs are: $(1,1),(1,3),(1,4),(2,2),(3,1),(3,3),(3,4),(4,1),(4,3),$ and $(4,4)$.

Test case $2$: There are $9$ pairs of $(i,j)$ $(1≤ i,j ≤ N)$ satisfying the condition. These pairs are: $(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),$ and $(3,3)$.

Source: codechef | Difficulty: HARD
Tags: Bit manipulation

Data structures

Mathematics


Solutions:
from collections import Counter

def solve(n, arr, x):
	positions = set()
	for i in range(x.bit_length()):
		if x & 1 << i > 0:
			positions.add(i)
	lookup = Counter()
	res = 0
	for num in arr:
		required = []
		for i in range(30):
			if i in positions:
				if num & 1 << i > 0:
					required.append(1)
				else:
					required.append(0)
		required = tuple(required)
		res += lookup[required] * 2
		lookup[required] += 1
	return res + n
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = int(input())
	print(solve(n, arr, x))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = int(input())
	if x == 0:
		le = len(l)
		print(le ** 2)
		continue
	y = bin(x)
	x = []
	for i in range(1, len(y) - 1):
		if y[-i] == '1':
			x.append(i)
	a = {}
	for i in l:
		j = bin(i)
		k = len(j) - 2
		s = ''
		for m in x:
			if k >= m:
				s = j[-m] + s
			else:
				s = '0' + s
				break
		k = int(s, 2)
		if k in a:
			a[k] += 1
		else:
			a[k] = 1
	c = 0
	for i in a:
		c += a[i] ** 2
	print(c)


import sys
import os
import math
from collections import *
import bisect
from heapq import *
from itertools import permutations
if os.path.exists('input.txt') and os.path.exists('output.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
input = sys.stdin.readline

def lcm(a, b):
	k1 = math.gcd(a, b)
	k2 = a * b
	return k2 // k1

def inp():
	return map(int, input().strip().split(' '))

def lis():
	return list(inp())
mod = 998244353

def prim(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True
ma = 2 * (10 ** 5 + 1)

def update(ind, val, n):
	while ind <= n:
		fenwick[ind] += val
		ind += ind & -ind

def qsum(ind):
	ans = 0
	while ind > 0:
		ans += fenwick[ind]
		ind -= ind & -ind
	return ans

def dfs(adj, vis, u, l):
	vis[u] = 1
	l.add(u)
	for i in adj[u]:
		if vis[i] == 0:
			dfs(adj, vis, i, l)
mod = 10 ** 9 + 7
ma = 1002
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def dfs(i, j, arr, vis, n, m):
	vis[i][j] = 1
	for x in range(4):
		mx = i + dx[x]
		my = j + dy[x]
		if mx >= 0 and mx < n and (my >= 0) and (my < m) and (vis[mx][my] == 0):
			if arr[i][j] >= arr[mx][my]:
				dfs(mx, my, arr, vis, n, m)

def dfs(a, vis, node, c):
	vis[node] = 1
	c[0] += 1
	if vis[a[node]] == 0:
		dfs(a, vis, a[node], c)
mod = 998244353

def f(n):
	if n % 4 == 0:
		return n
	if n % 4 == 1:
		return 1
	if n % 4 == 2:
		return n + 1
	return 0

def cn(n):
	s = str(n)
	if s == s[::-1]:
		return True
	return False

def f(n):
	i = 1
	res = 0
	while i <= math.sqrt(n):
		if n % i == 0:
			if cn(i):
				res += 1
			k = n // i
			if i != k and cn(k):
				res += 1
		i = i + 1
	return res
mod = 10 ** 9 + 7

def finv(p, q):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def solve():
	n = int(input())
	a = lis()
	x = int(input())
	d = {}
	for i in range(n):
		k = a[i] & x
		d[k] = d.get(k, 0) + 1
	ans = 0
	for i in d:
		ans += d[i] ** 2
	print(ans)
t = int(input())
for _ in range(t):
	solve()


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	X = int(input())
	hast = {}
	for i in A:
		if i & X in hast:
			hast[i & X] += 1
		else:
			hast[i & X] = 1
	res = 0
	for i in hast:
		res += hast[i] ** 2
	print(res)


for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	k = int(input())
	ans = 0
	d = {}
	for i in range(n):
		a[i] = a[i] & k
		if a[i] in d:
			d[a[i]] += 1
		else:
			d[a[i]] = 1
	for k in d:
		ans += d[k] * d[k]
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = int(input())
	indices_by_and = defaultdict(list)
	for (idx, i) in enumerate(arr):
		indices_by_and[i & x].append(idx + 1)
	ans = 0
	for v in indices_by_and.values():
		ans += len(v)
		ans += (len(v) - 1) * len(v)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	hashmap = {}
	for i in range(n):
		a[i] = a[i] & x
		if a[i] in hashmap:
			hashmap[a[i]] += 1
		else:
			hashmap[a[i]] = 1
	res = 0
	for k in hashmap:
		res += hashmap[k] ** 2
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = int(input())
	d = {}
	for e in l:
		andd = e & x
		if andd in d.keys():
			d[andd] += 1
		else:
			d[andd] = 1
	count = 0
	for k in d.keys():
		count += d[k] * d[k]
	print(count)


import math
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	X = int(input())
	for i in range(N):
		A[i] = A[i] & X
	D = {}
	for i in range(N):
		if A[i] not in D:
			D[A[i]] = 1
		else:
			D[A[i]] += 1
	ans = N
	for i in D.keys():
		ans += int(D[i] * (D[i] - 1) / 2) * 2
	print(ans)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	X = int(input())
	cnt = 0
	d = {}
	for i in range(N):
		A[i] = A[i] & X
		if A[i] in d:
			d.update({A[i]: d[A[i]] + 1})
		else:
			d.update({A[i]: 1})
	for i in d.values():
		cnt += i * i
	print(cnt)


for _ in range(int(input())):
	sdf = input()
	l = [int(i) for i in input().split()]
	x = int(input())
	for i in range(len(l)):
		l[i] = l[i] & x
	ans = 0
	d = dict()
	for i in range(len(l)):
		if l[i] in d:
			d[l[i]] += 1
		else:
			d[l[i]] = 1
	for i in d.values():
		ans += i * i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = int(input())
	d = {}
	for num in arr:
		if num & x in d:
			d[num & x] += 1
		else:
			d[num & x] = 1
	res = 0
	for num in arr:
		res += d[num & x]
	print(res)


t = int(input())
for z in range(t):
	n = int(input())
	arr = [k for k in map(int, input().split())]
	x = int(input())
	ans = []
	s = dict()
	c = 0
	for i in range(0, n):
		if arr[i] & x in s:
			s[arr[i] & x] += 1
		else:
			s[arr[i] & x] = 1
	for j in s.values():
		c = c + j * j
	print(c)


from itertools import groupby
T = int(input())
for _ in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	X = int(input())
	b = []
	for v in a:
		b.append(v & X)
	answer = 0
	b.sort()
	groups = groupby(b)
	for g in groups:
		cnt = len(list(g[1]))
		answer += cnt ** 2
	print(answer)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	for i in range(n):
		a[i] = a[i] & x
	dic = {}
	for i in a:
		if i in dic.keys():
			dic[i] += 1
		else:
			dic[i] = 1
	ans = 0
	for i in dic.values():
		ans += i ** 2
	print(ans)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	res = 0
	for i in range(n):
		a[i] = a[i] & x
	newa = dict(Counter(a))
	for j in newa.keys():
		res += newa[j] * newa[j]
	print(res)


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	for i in range(n):
		a[i] = a[i] & x
	d = dict(Counter(a))
	res = 0
	for k in d.keys():
		res += d[k] * d[k]
	print(res)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	for i in range(n):
		a[i] = a[i] & x
	d = dict(Counter(a))
	ans = 0
	for (key, val) in d.items():
		ans += val * val
	print(ans)


from collections import Counter
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	X = int(input())
	for i in range(N):
		A[i] = A[i] & X
	ans = 0
	my_dict = Counter(A)
	for _ in my_dict.values():
		ans += _ * _
	print(ans)


def ans(arr, x):
	i = 0
	cpy = arr.copy()
	while i != len(arr):
		arr[i] = x & arr[i]
		i += 1
	dist = set(arr)
	dict = {}
	for y in dist:
		dict[y] = []
	for (y1, y2) in zip(cpy, arr):
		dict[y2].append(y1)
	pairs = 0
	for y in dict:
		pairs += len(dict[y]) ** 2
	return pairs
test_cases = int(input())
while test_cases != 0:
	d = input()
	d2 = list(map(int, input().split()))
	d3 = int(input())
	print(ans(d2, d3))
	test_cases -= 1


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	x = int(input())
	y = [int(i) & x for i in a]
	z = Counter(y)
	an = 0
	for i in z.values():
		an += i * (i - 1)
	print(an + n)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = int(input())
	d = dict()
	for i in range(n):
		temp = x & l[i]
		if temp in d.keys():
			d[temp] += 1
		else:
			d[temp] = 1
	ans = 0
	for (x, y) in d.items():
		ans += y * y
	print(ans)


from collections import Counter
T = int(input())
for tc in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	x = int(input())
	for i in range(len(arr)):
		arr[i] = arr[i] & x
	p = Counter(arr)
	ans = 0
	for i in p:
		ans += p[i] * p[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = int(input())
	mp = {}
	ans = 0
	for i in arr:
		k = i & x
		mp[k] = mp.get(k, 0) + 1
	for (i, j) in mp.items():
		ans += j * j
	print(ans)


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	x = int(input())
	d = dict()
	result = 0
	for i in l:
		k = i & x
		d[k] = d.get(k, 0) + 1
	for i in d.keys():
		result += d[i] ** 2
	print(result)
t = int(input())
while t:
	solve()
	t -= 1


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = int(input())
	a = [i & x for i in l]
	c = Counter(a)
	t = 0
	for v in c.values():
		if v > 1:
			t += v * (v - 1)
	print(t + n)


import sys, math
from tkinter import Y
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = int(input())
	d = {}
	for i in range(n):
		y = l[i] & x
		if y in d:
			d[y] = d[y] + 1
		else:
			d[y] = 1
	ans = 0
	for i in d:
		ans = ans + d[i] * d[i]
	print(ans)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	x = int(input())
	temp = []
	for i in li:
		temp.append(i & x)
	c = Counter(temp)
	sum = 0
	for i in c:
		sum += c[i] ** 2
	print(sum)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	x = int(input())
	cnt = defaultdict(int)
	for i in range(n):
		a[i] = a[i] & x
		cnt[a[i]] += 1
	ans = 0
	for i in cnt:
		ans += cnt[i] ** 2
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	x = int(input())
	new_arr = list(map(lambda i: i & x, nums))
	hash_map = dict()
	for i in new_arr:
		if i in hash_map:
			hash_map[i] = 1 + hash_map.get(i)
		else:
			hash_map[i] = 1
	cnt = 0
	for (key, value) in hash_map.items():
		cnt += value * value
	print(cnt)


for _ in range(int(input())):
	coun = 0
	n = int(input())
	l = list(map(int, input().split()))
	k = int(input())
	l = [i & k for i in l]
	d = {}
	for i in l:
		if i not in d.keys():
			d[i] = 1
		else:
			d[i] += 1
	for i in d.values():
		coun += i * i
	print(coun)


import math as m

def ncr(N, R):
	return m.factorial(N) // (m.factorial(R) * m.factorial(N - R))

def getL():
	return [int(i) for i in input().split(' ')]

def getInt():
	return int(input())

def solve():
	n = getInt()
	arr = getL()
	x = getInt()
	d = {}
	for i in arr:
		t = i & x
		if t not in d:
			d[t] = 1
		else:
			d[t] += 1
	print(sum([v * v for v in d.values()]))
for _ in range(getInt()):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = int(input())
	d = {}
	for i in a:
		d[i & k] = d.get(i & k, 0) + 1
	ans = 0
	for i in d.values():
		ans += i * i
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	ans = 0
	a = list(map(int, input().split()))
	x = int(input())
	d = dict()
	for i in range(n):
		d[x & a[i]] = 0
	for i in range(n):
		d[x & a[i]] += 1
	for i in d.values():
		if i > 1:
			ans += i * (i - 1) // 2
	print(ans * 2 + n)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = int(input())
	c = 0
	for i in range(n):
		l[i] &= x
	d = {}
	for i in l:
		if i in d.keys():
			d[i] += 1
		else:
			d[i] = 1
	for j in d.values():
		c += j * j
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	for i in range(len(a)):
		a[i] = a[i] & x
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	cnt = 0
	for i in d.values():
		cnt += i ** 2
	print(cnt)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	x = int(input())
	d = {}
	ans = 0
	for i in range(n):
		arr[i] = arr[i] & x
	for ele in arr:
		d[ele] = d.get(ele, 0) + 1
	for ele in d:
		n = d[ele]
		ans += n * n
	print(ans)


import math
from collections import Counter

def solve():
	a_and = [a_i & x for a_i in a]
	d = Counter(a_and)
	return sum([i ** 2 for i in d.values()])
T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	print(solve())


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	d = {}
	for i in a:
		y = i & x
		if y in d:
			d[y] += 1
		else:
			d[y] = 1
	b = 0
	for i in d:
		b += d[i] ** 2
	print(b)


def calculate():
	r = []
	total = 0
	d = {}
	for i in range(N):
		r.append(arr[i] & X)
	for i in range(N):
		if d.get(r[i], 0):
			d[r[i]] += 1
		else:
			d[r[i]] = 1
	for ele in d.values():
		total = total + ele * ele
	return total
T = int(input())
for _ in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	X = int(input())
	print(calculate())


from collections import Counter
for i in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	x = int(input())
	r = []
	res = n
	for i in range(len(l)):
		r.append(l[i] & x)
	r = sorted(r)
	k = 0
	j = 0
	s = dict(Counter(r))
	for i in s:
		k += (s[i] - 1) * s[i]
	res += k
	print(res)


from collections import Counter
for i in range(int(input())):
	(n, s, x) = (int(input()), input(), int(input()))
	for i in Counter(map(lambda i: int(i) & x, s.split())).values():
		n += i * (i - 1)
	print(n)


from sys import stdin, stdout
from collections import defaultdict, Counter
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	x = int(input().strip())
	temp = list()
	for num in arr:
		temp.append(num & x)
	d = Counter(temp)
	ans = 0
	for key in d:
		val = d[key]
		ans += val * val
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	dic = defaultdict(int)
	for i in range(n):
		dic[a[i] & x] += 1
	ans = 0
	for i in dic:
		ans += dic[i] * (dic[i] - 1)
	print(ans + n)


from collections import defaultdict
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	d = defaultdict(lambda : 0)
	ans = 0
	for j in a:
		c = j & x
		d[c] += 1
	for j in d.keys():
		c = d[j]
		c = c * (c + 1) - c
		ans += c
	print(ans)


from sys import stdin
input = stdin.readline

def solve(N, A, X):
	A = [a & X for a in A]
	frequency = {}
	for a in A:
		if a not in frequency:
			frequency[a] = 0
		frequency[a] += 1
	return sum((frequency[f] ** 2 for f in frequency))
T = int(input().strip())
for problem in range(1, T + 1):
	N = int(input().strip())
	A = [int(x) for x in input().strip().split()]
	X = int(input().strip())
	print(solve(N, A, X))


import math
T = int(input())
for _ in range(T):
	X = int(input())
	l = list(map(int, input().split()))
	N = int(input())
	a = 0
	b = 0
	d = dict()
	for i in l:
		if i & N == 0:
			a += 1
		elif i & N == N:
			b += 1
		elif i & N in d.keys():
			d[i & N] += 1
		else:
			d[i & N] = 1
	s = a * (a - 1) + b * (b - 1) + X
	for i in d.values():
		s += i * (i - 1)
	print(s)


def fact(n, memo={}):
	if n in memo:
		return memo[n]
	if n == 1:
		return 1
	memo[n] = n * fact(n - 1, memo)
	return memo[n]

def main(x, arr):
	ans = 0
	d = {}
	for i in arr:
		if x & i in d:
			d[x & i] += 1
		else:
			d[x & i] = 1
	for i in d.values():
		ans += i * (i - 1)
	return ans + len(arr)
t = int(input())
while t:
	_ = int(input())
	arr = list(map(int, input().split()))
	x = int(input())
	print(main(x, arr))
	t -= 1


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = int(input())
	c = 0
	for j in range(n):
		arr[j] = arr[j] & x
	dnary = {}
	for j in range(n):
		if arr[j] not in dnary:
			dnary[arr[j]] = 1
		else:
			dnary[arr[j]] += 1
	l = list(dnary.values())
	ans = 0
	for k in l:
		ans += k * k
	print(ans)


from collections import Counter
k = int(input())
while k:
	k -= 1
	t = int(input())
	l = list(map(int, input().split()))
	m = int(input())
	f = []
	for i in l:
		f.append(i & m)
	j = Counter(f)
	sum = 0
	for i in j:
		sum += j[i] ** 2
	print(sum)


from collections import Counter
for tcase in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	c = Counter([x & y for y in a])
	print(sum((c[k] * c[k] for k in c)))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = int(input())
	a = [0] * n
	for i in range(len(arr)):
		a[i] = arr[i] & x
	mp = Counter(a)
	ans = n
	for k in mp.keys():
		if mp[k] > 1:
			ans += mp[k] * (mp[k] - 1)
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	l = []
	count = 0
	for i in range(n):
		flag = 0
		for j in range(20):
			if 1 << j & x and 1 << j & a[i]:
				flag = 1
				break
		if flag == 1:
			l.append(a[i])
		else:
			count += 1
	d = dict()
	res = count * count
	for i in l:
		count = 0
		for j in range(20):
			if 1 << j & x:
				count += 1 << j & i
		if count in d.keys():
			d[count] += 1
		else:
			d[count] = 1
	for i in d.values():
		res += i * i
	print(res)
	t -= 1


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
mod = 10 ** 4

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

def nextPowerOf2(n):
	count = 0
	if n and (not n & n - 1):
		return n
	while n != 0:
		n >>= 1
		count += 1
	return 1 << count
from collections import defaultdict
import math

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

def upper_bound(arr, target):
	start = 0
	end = len(arr) - 1
	ans = -1
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] <= target:
			start = mid + 1
		else:
			ans = mid
			end = mid - 1
	return ans

def get_dis(s1, s2):
	s = 'abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz'
	a1 = s.index(s1)
	a2 = s.rfind(s1)
	b1 = s.index(s2)
	b2 = s.rfind(s2)
	return min(abs(a1 - b1), abs(a1 - b2), abs(a2 - b1), abs(a2 - b2))
from collections import defaultdict

def func(l, m):
	ans = 0
	s = set()
	for ele in l:
		ans += ele % m
		print(ans, ele % m, ele, m)
		if ele % m in s:
			return -1
	print('tot', len(l) * (len(l) + 1) // 2, ans)
	if ans == len(l) * (len(l) + 1) // 2:
		return 1
	return 0

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

def func(x):
	c = 0
	while x != 0 and x % 2 == 0:
		x = x // 2
		c += 1
	return c
INF = 1000000000000000000000
from collections import deque
import math

def solve():
	d = defaultdict(int)
	n = int(input())
	lis = list(map(int, input().split()))
	x = int(input())
	for i in range(len(lis)):
		lis[i] &= x
		d[lis[i]] += 1
	ans = 0
	for (k, v) in d.items():
		ans += v * (v - 1)
	print(ans + n)
num_test = 1
num_test = int(input())
for _ in range(num_test):
	solve()


from collections import Counter, deque, defaultdict
from math import *

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	arr = []
	ans = 0
	for i in range(n):
		if x & a[i]:
			arr.append(a[i])
		else:
			ans += 1
	ans *= ans
	d = defaultdict(int)
	for i in arr:
		d[i & x] += 1
	for i in d.keys():
		ans += d[i] ** 2
	print(ans)
testCases = int(input())
for i in range(testCases):
	solve()


from typing import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = int(input())
	for i in range(n):
		l[i] &= x
	d = Counter(l)
	ans = n
	for j in d.values():
		ans += j * (j - 1)
	print(ans)


try:
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		x = int(input())
		c = n
		d = {}
		for i in range(n):
			l[i] &= x
			d[l[i]] = d.get(l[i], 0) + 1
		for i in d:
			c += d[i] * (d[i] - 1) // 2 * 2
		print(c)
except:
	pass


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		x = int(input())
		d = dict()
		for i in range(n):
			val = arr[i] & x
			d[val] = d.get(val, 0) + 1
		ans = 0
		for k in d:
			ans += d[k] * (d[k] - 1)
		print(ans + n)
except:
	pass


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = int(input())
	arr = [i & x for i in arr]
	c = Counter(arr)
	ans = 0
	for i in c:
		ans += c[i] * c[i]
	print(ans)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = int(input())
	new_arr = []
	for i in arr:
		new_arr.append(i & x)
	cntr = Counter(new_arr)
	s = 0
	for i in cntr:
		s += cntr[i] ** 2
	print(s)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	k = int(input())
	b = []
	for i in l:
		b.append(i & k)
	g = Counter(b)
	s = 0
	for i in g:
		s += g[i] ** 2
	print(s)


to = int(input())
import collections
while to > 0:
	no = int(input())
	ao = input().split()
	for i in range(no):
		ao[i] = int(ao[i])
	xo = int(input())
	d = collections.defaultdict(int)
	for i in range(no):
		ao[i] = ao[i] & xo
		d[ao[i]] += 1
	anos = 0
	for i in range(no):
		if d[ao[i]] > 0:
			anos += d[ao[i]] * d[ao[i]]
			d[ao[i]] = 0
	print(anos)
	anos = 0
	a = 0
	b = 0
	(c, d, e) = (0, 0, 1)
	to -= 1


import math

def npr(n):
	return n * (n - 1)
for tc in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = int(input())
	for i in range(n):
		l[i] = l[i] & x
	l.sort()
	l.append(-1)
	(c, s) = (1, 0)
	for i in range(1, n + 1):
		if l[i] != l[i - 1]:
			if i != 1:
				s += npr(c)
			c = 1
		else:
			c += 1
	print(s + n)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	k = int(input())
	for i in range(len(arr)):
		arr[i] = arr[i] & k
	setx = Counter(arr)
	res = 0
	for (i, c) in setx.items():
		res += c * c
	print(res)


class Node:

	def __init__(self):
		self.left = None
		self.right = None
		self.count = 0

class Trie:

	def __init__(self):
		self.master = Node()

	def insert(self, binary):
		self._insert(binary, 30, self.master)

	def _insert(self, binary, bitNo, node):
		if bitNo == -1:
			node.count += 1
			return
		if binary & 1 << bitNo:
			if not node.right:
				node.right = Node()
			self._insert(binary, bitNo - 1, node.right)
		else:
			if not node.left:
				node.left = Node()
			self._insert(binary, bitNo - 1, node.left)

	def search(self, binary):
		node = self.master
		for i in range(30, -1, -1):
			if binary & 1 << i == 0:
				if node.left:
					node = node.left
				else:
					return 0
			elif node.right:
				node = node.right
			else:
				return 0
		return node.count
from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	k = int(input())
	for i in range(len(arr)):
		arr[i] = arr[i] & k
	setx = Counter(arr)
	res = 0
	for (i, c) in setx.items():
		res += c * c
	print(res)


def find_substr(string, indexes):
	s = ''
	for i in indexes:
		if len(string) - i >= 0:
			s += string[len(string) - i]
	return s
T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	X = int(input())
	X = '{0:b}'.format(X)
	b = [len(X) - idx for (idx, v) in enumerate(X) if v == '1']
	M = len(X)
	ans = dict()
	for i in range(N):
		a = str('{0:b}'.format(A[i])).zfill(M + 1)
		a = find_substr(a, b)
		if a in ans.keys():
			ans[a] += 1
		else:
			ans[a] = 1
	x = 0
	for k in ans.keys():
		x += ans[k] ** 2
	print(x)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	for i in range(n):
		a[i] = a[i] & x
	d = Counter(a)
	a = list(d.keys())
	ans = 0
	n = len(a)
	for i in range(n):
		b = x & a[i]
		ans += d[a[i]] * d[b]
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	for i in range(n):
		a[i] = a[i] & x
	ans = 0
	a.sort()
	cur = 1
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			cur += 1
		else:
			ans = ans + cur * cur
			cur = 1
	ans = ans + cur * cur
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = [int(x) for x in input().split()]
	x = int(input())
	b = bin(x).replace('0b', '')
	d = []
	b = b[::-1]
	if len(set(s)) == 1:
		print(n * n)
		continue
	for i in range(len(b)):
		if b[i] == '1':
			d.append(i)
	arr = []
	q1 = [s]
	di = {}
	for i in s:
		q = bin(i).replace('0b', '')
		q = q[::-1]
		di[i] = q
	for i in d:
		q2 = []
		for j in q1:
			mat = []
			mat1 = []
			for k in j:
				z = di[k]
				if len(z) > i and z[i] == '1':
					mat.append(k)
				else:
					mat1.append(k)
			q2.append(mat)
			q2.append(mat1)
		q1 = q2
	ans = 0
	for i in q1:
		q = len(i)
		ans += q * q
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	x = int(input())
	lk = {}
	pos = []
	target = 0
	for i in range(30):
		if 1 << i & x > 0:
			pos.append(i)
			target |= 1 << i
	ans = 0
	for i in range(n):
		num = ar[i]
		curr = 0
		for bit in pos:
			curr = curr | 1 << bit & num
		if curr in lk:
			ans += lk[curr]
			lk[curr] += 1
		else:
			lk[curr] = 1
	print(2 * ans + n)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		n = inpu()
		arr = lis()
		x = inpu()
		arr = [i & x for i in arr]
		c = Counter(arr)
		ans = 0
		for i in c:
			ans += c[i] * c[i]
		print(ans)
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	b = {}
	s = 0
	for i in range(n):
		try:
			b[a[i] & x] += 1
		except:
			b[a[i] & x] = 1
	for i in b:
		s += b[i] ** 2
	print(s)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = int(input())
	l2 = []
	for i in l:
		l2.append(i & x)
	d = dict()
	for j in l2:
		if j in d:
			d[j] += 1
		else:
			d[j] = 1
	sm = 0
	for k in d:
		v = d[k]
		val = v * (v - 1)
		sm += val
	sm += n
	print(sm)


import collections
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	M = int(input())
	B = []
	for i in range(N):
		B.append(A[i] & M)
	ans = 0
	C = collections.Counter(B)
	val = C.values()
	for i in val:
		ans += i * i
	print(ans)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	x = int(input())
	for i in range(n):
		l[i] = l[i] & x
	d = {}
	for i in range(n):
		if l[i] not in d:
			d[l[i]] = 1
		else:
			d[l[i]] += 1
	count = 0
	for (i, j) in d.items():
		count += j * j
	print(count)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = int(input())
	dcit = {}
	if x == 0 or a == [0] * n:
		print(n * n)
		continue
	for j in a:
		ar = j & x
		if ar in dcit:
			dcit[ar] += 1
		else:
			dcit[ar] = 1
	ans = 0
	for j in dcit.values():
		ans += j * j
	print(ans)


t = int(input())
import collections
while t > 0:
	n = int(input())
	a = input().split()
	for i in range(n):
		a[i] = int(a[i])
	x = int(input())
	d = collections.defaultdict(int)
	for i in range(n):
		a[i] = a[i] & x
		d[a[i]] += 1
	ans = 0
	for i in range(n):
		if d[a[i]] > 0:
			ans += d[a[i]] * d[a[i]]
			d[a[i]] = 0
	print(ans)
	t -= 1


from collections import Counter

def solve():
	N = int(input())
	A = list(map(int, input().split()))
	X = int(input())
	AX = [a & X for a in A]
	d = Counter(AX)
	ans = 0
	for k in d.keys():
		ans += d[k] ** 2
	print(ans)
T = int(input())
for _ in range(T):
	solve()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = int(input())
	dit = {}
	for e in arr:
		a = e & x
		if a in dit:
			dit[a] += 1
		else:
			dit[a] = 1
	ans = 0
	for e in dit.values():
		ans += e ** 2
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	x = int(input())
	s = bin(x).replace('0b', '')
	l = len(s)
	s = '0' * (32 - l) + s
	ind0 = []
	for j in range(32):
		if s[j] == '1':
			ind0.append(j)
	lst1 = []
	for j in lst:
		s = bin(j).replace('0b', '')
		l = len(s)
		s = '0' * (32 - l) + s
		ans = ''
		for g in ind0:
			ans += s[g]
		lst1.append(ans)
	dic = {}
	for j in lst1:
		dic[j] = 0
	for j in lst1:
		dic[j] += 1
	c = 0
	for j in dic.keys():
		if dic[j] > 1:
			ele = dic[j]
			ad = ele * (ele - 1)
			c += ad
	print(c + n)


T = int(input())
from collections import defaultdict
for _ in range(T):
	N = int(input())
	lst = list(map(int, input().split()))
	X = int(input())
	d = defaultdict(int)
	ans = 0
	if X == 0:
		ans = N * N
	else:
		for i in range(N):
			lst[i] = lst[i] & X
			d[lst[i]] += 1
		for v in d.values():
			ans += v * v
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = int(input())
	d = {}
	for i in range(n):
		a = l[i] & x
		if a in d.keys():
			d[a] += 1
		else:
			d[a] = 1
	y = list(d.values())
	count = 0
	for j in range(len(y)):
		b = y[j] ** 2
		count += b
	print(count)


for t in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	k = int(input())
	data = {}
	output = 0
	for i in arr:
		if i & k in data:
			data[i & k] += 1
		else:
			data[i & k] = 1
	for i in data:
		output += data[i] ** 2
	print(output)


testcase = int(input())
while testcase > 0:
	n = int(input())
	arr = list(map(int, input().split(' ')))
	x = int(input())
	count = {}
	for i in arr:
		num = i & x
		count[num] = count.get(num, 0) + 1
	res = 0
	for (i, j) in count.items():
		res += j * j
	print(res)
	testcase -= 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = int(input())
	m = set()
	for i in range(32, -1, -1):
		if x >> i & 1:
			m.add(i)
	d = {}
	ans = 0
	for el in arr:
		temp = ''
		for b in m:
			if el >> b & 1:
				temp += '1'
			else:
				temp += '0'
		if temp not in d:
			d[temp] = 0
		ans += d[temp]
		d[temp] += 1
	print(ans * 2 + n)