Chef was impressed by an array A of N non-negative integers. But, he was asked to solve the following problem in order to get this array.

Given a non-negative integer k, find the number of pairs (i, j) (1 ≤ i < j ≤ N) such that the following condition holds true:  
(A_{i} | A_{j}) + (A_{i} \oplus A_{j}) + (A_{i} \& A_{j}) = k + A_{j}, where 
(A_{i} | A_{j}) denotes [Bitwise OR] operation,
(A_{i} \oplus A_{j}) denotes [Bitwise XOR] operation,
(A_{i} \& A_{j}) denotes [Bitwise AND] operation.

You, being Chef's friend, help him get this array by solving the above problem.

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

- The first line contains an integer T, the number of test cases.
- The first line of each test case contains two space-separated integers N and k, the number of integers in the array A and the non-negative integer k respectively.
- The next line contains N space-separated non-negative integers A_{1},A_{2}, \ldots, A_{N}, the elements of the array A.

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

For each test case, print a single line containing the number of pairs satisfying the mentioned condition.

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

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

----- Sample Input 1 ------ 
2
1 8
7
3 8
1 6 4
----- Sample Output 1 ------ 
0
2
----- explanation 1 ------ 
Test case $1$: The input array contains only a single integer. Thus, no pairs are possible.

Test case $2$: There are two pairs satisfying the condition -
- $(i,j) = (1, 2)$: $A_{1} = 1$ and $A_{2} = 6$. Thus, $(1|6) + (1\oplus 6) + (1$ $\&$ $6) = 7 + 7 + 0 = 14$. Also, $k+A_{2} = 8 + 6 = 14$.
- $(i,j) = (2, 3)$: $A_{2} = 6$ and $A_{3} = 4$. Thus, $(6|4) + (6\oplus 4) + (6$ $\&$ $4) = 6 + 2 + 4 = 12$. Also, $k+A_{3} = 8 + 4 = 12$.

Difficulty: HARD
Tags: String algorithms

Bit manipulation

Data structures

Mathematics
Skill types: Bit manipulation

Data structures

Starter code:

Solutions:
T = int(input())
for t in range(1, T + 1):
	inp = input().split()
	N = int(inp[0])
	K = int(inp[1])
	A = list(map(int, input().split()))
	cnt = 0
	freq = {}
	for a in A:
		if a in freq.keys():
			cnt += freq[a]
		val = K - a ^ a
		if val in freq.keys():
			freq[val] += 1
		else:
			freq[val] = 1
	print(cnt)


import sys, os
from sys import stdin, stdout
io_path = 'E:\\Personal\\competitve-programming\\IO'
if os.path.exists(io_path):
	sys.stdout = open(io_path + '/output.txt', 'w')
	sys.stdin = open(io_path + '/input.txt', 'r')

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

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

def get_string():
	return input().strip()
test_cases = int(input())
while test_cases > 0:
	(n, k) = get_ints()
	arr = get_ints_list()
	aux = {}
	ans = 0
	for i in arr:
		res = k - i ^ i
		if i in aux:
			ans += aux[i]
		else:
			aux[i] = 0
		if res in aux:
			aux[res] += 1
		else:
			aux[res] = 1
	print(ans)
	test_cases -= 1


for _ in range(int(input())):
	(N, k) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	counter = 0
	my_dict = {}
	for i in range(N):
		if A[i] in my_dict:
			my_dict[A[i]] += 1
		else:
			my_dict[A[i]] = 1
	for i in range(N):
		val = k - A[i] ^ A[i]
		if val in my_dict:
			counter += my_dict[val]
			if A[i] == val:
				counter -= 1
		my_dict[A[i]] -= 1
	print(counter)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	dict_count = {}
	for idx in range(n):
		if arr[idx] in dict_count:
			dict_count[arr[idx]] += 1
		else:
			dict_count[arr[idx]] = 1
	res = 0
	for idx in range(n):
		temp = k - arr[idx] ^ arr[idx]
		if temp in dict_count:
			res += dict_count[temp]
			if arr[idx] == temp:
				res = res - 1
		dict_count[arr[idx]] -= 1
	print(res)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	d = {}
	ans = 0
	for x in arr:
		try:
			ans += d[x]
		except:
			pass
		if x <= k:
			ele = x ^ k - x
			try:
				d[ele] += 1
			except:
				d[ele] = 1
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	d = defaultdict(int)
	l = list(map(int, input().split()))
	sm = 0
	for i in range(n):
		x = d[l[i]]
		sm += x
		z = k - l[i] ^ l[i]
		d[z] += 1
	print(sm)


from collections import Counter
R = int(input())
while R:
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	hash = Counter()
	ans = 0
	for i in range(N):
		ans += hash[A[i]]
		hash[K - A[i] ^ A[i]] += 1
	print(ans)
	R -= 1


T = int(input())
for i in range(T):
	Nk = str(input()).split(' ')
	N = int(Nk[0])
	k = int(Nk[1])
	A = str(input()).split(' ')
	dicto = {}
	total = 0
	for j in range(N):
		total = total + dicto.get(int(A[j]), 0)
		dicto[k - int(A[j]) ^ int(A[j])] = dicto.get(k - int(A[j]) ^ int(A[j]), 0) + 1
	print(total)


import sys
import math
import bisect
import heapq
from bisect import bisect_right
from sys import stdin, stdout

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

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

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def myceil(x, y):
	return (x + y - 1) // y

def Solution():
	pass

def main():
	for _ in range(get_int()):
		(n, k) = get_ints_in_variables()
		a = get_ints_in_list()
		hm = {}
		ans = 0
		for v in a:
			if v in hm:
				ans += hm[v]
			aj = k - v ^ v
			if aj in hm:
				hm[aj] += 1
			else:
				hm[aj] = 1
		print(ans)
main()


def xor(a, k):
	return k - a ^ a

def ans(arr, k):
	d = {}
	answer = 0
	for y in arr:
		if y in d.keys():
			answer += d[y]
		t = xor(y, k)
		if t in d.keys():
			d[t] += 1
		else:
			d[t] = 1
	return answer
test_cases = int(input())
while test_cases != 0:
	d = list(map(int, input().split()))
	d2 = list(map(int, input().split()))
	print(ans(d2, d[1]))
	test_cases -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().strip().split(' '))
	v = list(map(int, input().strip().split(' ')))
	freq = {}
	ans = 0
	for i in range(0, n):
		if v[i] in freq.keys():
			ans += freq[v[i]]
		if k >= v[i]:
			req = k - v[i] ^ v[i]
			if req in freq.keys():
				freq[req] += 1
			else:
				freq[req] = 1
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	d = defaultdict(lambda : 0)
	for i in l:
		ans += d[i]
		d[k - i ^ i] += 1
	print(ans)


from collections import defaultdict as dd
t = int(input())
for _ in range(t):
	(n, k) = list((int(x) for x in input().split()))
	l = list((int(x) for x in input().split()))
	d = dd(int)
	res = 0
	for v in l[::-1]:
		v2 = k - v ^ v
		res += d[v2]
		d[v] += 1
	print(res)


import collections
T = int(input())
for _ in range(T):
	(P, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	D = collections.defaultdict(int)
	ans = 0
	for i in range(P):
		ans += D[A[i]]
		if A[i] <= Q:
			D[Q - A[i] ^ A[i]] += 1
	print(ans)


q = int(input())
for _ in range(q):
	inp = list(map(int, input().split()))
	n = inp[0]
	k = inp[1]
	a = list(map(int, input().split()))
	f = {}
	count = 0
	for i in range(n):
		b_i = k - a[i] ^ a[i]
		count += f.get(a[i], 0)
		if b_i in f:
			f[b_i] += 1
		else:
			f[b_i] = 1
	print(count)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	res = {}
	for i in range(n):
		oper = k - arr[i] ^ arr[i]
		if arr[i] in res:
			ans += res[arr[i]]
		if oper in res:
			res[oper] += 1
		else:
			res[oper] = 1
	print(ans)


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, k) = sep()
		arr = lis()
		c = Counter(arr)
		ans = 0
		for i in range(n):
			c[arr[i]] -= 1
			if arr[i] > k:
				continue
			ans += c[arr[i] ^ k - arr[i]]
		print(ans)
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	d = {}
	for i in range(n):
		if a[i] in d.keys():
			ans += d[a[i]]
		if k >= a[i]:
			b = k - a[i] ^ a[i]
			if b in d.keys():
				d[b] += 1
			else:
				d[b] = 1
	print(ans)


from collections import defaultdict
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	ans = 0
	D = defaultdict(int)
	for aj in map(int, input().split()):
		ans += D[aj]
		if aj <= K:
			D[aj ^ K - aj] += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().rstrip().split())
	l = list(map(int, input().rstrip().split()))
	d = dict()
	ans = 0
	for ele in l:
		ans += d.get(ele, 0)
		if k >= ele:
			x = k - ele ^ ele
			d[x] = d.get(x, 0) + 1
	print(ans)


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	net = collections.defaultdict(int)
	ans = 0
	for i in range(n):
		ans += net[A[i]]
		net[k - A[i] ^ A[i]] += 1
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	dict_ = {}
	ans = 0
	for i in range(a):
		if c[i] in dict_.keys():
			ans += dict_[c[i]]
		if b >= c[i]:
			dict_1 = b - c[i] ^ c[i]
			if dict_1 in dict_.keys():
				dict_[dict_1] += 1
			else:
				dict_[dict_1] = 1
	print(ans)


from collections import Counter as C
R = lambda : input()
I = lambda : int(R())
M = lambda : map(int, R().split())
RS = lambda : map(str, R().split(' '))
L = lambda : list(M())
for _ in range(I()):
	(n, k) = M()
	arr = L()
	c = C()
	ans = 0
	for i in range(n - 1, -1, -1):
		if k >= arr[i]:
			ans += c[arr[i] ^ k - arr[i]]
		c[arr[i]] += 1
	print(ans)


t = int(input())
for _ in range(t):
	lis = list(map(int, input().split()))
	(n, k) = (lis[0], lis[1])
	a = list(map(int, input().split()))
	count = 0
	dic = {}
	if n == 1:
		print(0)
	else:
		for i in range(n):
			aux = a[i] ^ k - a[i]
			if a[i] in dic:
				count += dic[a[i]]
			if aux not in dic:
				dic[aux] = 1
			else:
				dic[aux] += 1
		print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = [int(i) for i in input().split()]
	ans = 0
	n1 = max(s)
	d = dict()
	for i in range(n):
		t1 = k - s[i] ^ s[i]
		if s[i] in d:
			ans += d[s[i]]
		if t1 in d:
			d[t1] += 1
		else:
			d[t1] = 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	(memo, count) = ({}, 0)
	for i in a:
		count += memo.get(i, 0)
		memo[k - i ^ i] = memo.get(k - i ^ i, 0) + 1
	print(count)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	d = dict()
	ans = 0
	for i in range(n - 1, -1, -1):
		re = x - a[i] ^ a[i]
		if re in d.keys():
			ans += d[re]
		if a[i] in d.keys():
			d[a[i]] += 1
		else:
			d[a[i]] = 1
	print(ans)


import sys
import math
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase
from heapq import *

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline

def dist(x1, x2, y1, y2):
	return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

def mergeSort(arr, check=lambda a, b: a < b, reverse=False):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L, check, reverse)
		mergeSort(R, check, reverse)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if check(L[i], R[j]):
				if not reverse:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					j += 1
			elif not reverse:
				arr[k] = R[j]
				j += 1
			else:
				arr[k] = L[i]
				i += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

def maxSum(arr):
	max_sum = float('-inf')
	max_cur = 0
	for num in ar:
		max_cur = max(max_cur + num, num)
		if max_cur > max_sum:
			max_sum = max_cur
	return max_sum

def hcf(a, b):
	if b == 0:
		return a
	else:
		return hcf(b, b % a)

def get_power(n, m):
	i = 1
	p = -1
	while i <= n:
		i = i * m
		p += 1
	return p

def fact(n):
	f = 1
	for i in range(2, n + 1):
		f *= i
	return f

def find_closest(num, ar):
	min_d = float('inf')
	for num2 in ar:
		d = abs(num2 - num)
		if d < min_d:
			min_d = d
	return min_d

def check_pal(n):
	s = str(n)
	j = len(s) - 1
	i = 0
	while j > i:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True

def solve(t):
	(n, k) = readInts()
	ar = readList()
	dic = {}
	res = 0
	for i in range(n - 1, -1, -1):
		req = ar[i] ^ k - ar[i]
		if req in dic:
			res += dic[req]
		if ar[i] in dic:
			dic[ar[i]] += 1
		else:
			dic[ar[i]] = 1
	print(res)

def main():
	t = 1
	sys.setrecursionlimit(2000)
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


for t in range(int(input())):
	(N, k) = map(int, input().split())
	A = list(map(int, input().split()))
	A.reverse()
	count = 0
	d = dict()
	for i in A:
		count += d.get(k - i ^ i, 0)
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	print(count)


t = int(input())
while t > 0:
	t -= 1
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = [int(x) for x in input().split()]
	d = {}
	c = 0
	for i in range(n):
		x = a[i]
		x = x ^ k - x
		if a[i] in d.keys():
			c += d[a[i]]
		if x in d.keys():
			d[x] += 1
		else:
			d[x] = 1
	print(c)


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	d = defaultdict(int)
	ans = 0
	for el in arr:
		ans += d[el]
		d[el ^ k - el] += 1
	print(ans)


import collections
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = [int(x) for x in input().split()]
	d = collections.defaultdict(lambda : 0)
	cnt = 0
	for i in range(n - 1, -1, -1):
		tmp = k - s[i] ^ s[i]
		cnt += d[tmp]
		d[s[i]] += 1
	print(cnt)


import math
import bisect
import heapq
from math import gcd, floor, sqrt, log
from collections import defaultdict as ddc
from collections import Counter

def intin():
	return int(input())

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

def strin():
	return input().split()
INF = 10 ** 20
mod = 1000000007

def exponentiation(bas, exp, mod=1000000007):
	t = 1
	while exp > 0:
		if exp % 2 != 0:
			t = t * bas % mod
		bas = bas * bas % mod
		exp //= 2
	return t % mod

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

def process(arr, n, k):
	val = ddc(int)
	ans = 0
	for ele in arr:
		ans += val[ele]
		if ele <= k:
			val[ele ^ k - ele] += 1
	return ans

def main():
	for _ in range(int(input())):
		(n, k) = mapin()
		arr = list(mapin())
		print(process(arr, n, k))
main()


from collections import defaultdict
for tcase in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	d = defaultdict(int)
	for aj in map(int, input().split()):
		ans += d[aj]
		if aj <= k:
			d[aj ^ k - aj] += 1
	print(ans)


import sys
import os
import math
from collections import *
import bisect
from heapq import *
from itertools import permutations, combinations
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
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, k) = inp()
	a = lis()
	d = {}
	ans = 0
	for i in range(n - 1, -1, -1):
		if k < a[i]:
			d[a[i]] = d.get(a[i], 0) + 1
			continue
		res = k - a[i] ^ a[i]
		if res in d:
			ans += d[res]
		d[a[i]] = d.get(a[i], 0) + 1
	print(ans)
t = int(input())
for _ in range(t):
	solve()


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	d = dict()
	a = list(map(int, input().split()))
	b = []
	for i in range(n):
		b.append(k - a[i])
		if a[i] in d:
			d[a[i]] += 1
		else:
			d[a[i]] = 1
	ans = 0
	for i in range(n):
		if b[i] < 0:
			pass
		else:
			num = a[i] ^ b[i]
			if num == a[i]:
				ans += d[num] - 1
			elif num in d:
				ans += d[num]
		d[a[i]] -= 1
	print(ans)