Chef and his friends would like to attend a large New Year's party in Goa. However, their teacher has given them an assignment to complete. Chef asked for your help to complete the assignment quickly so that he can attend the party with complete freedom.

Chef was given an array A = [A_{1}, A_{2}, \ldots, A_{N}] of length N, an array B = [B_{1}, B_{2}, \ldots, B_{M}] of length M, and a prime number P. His task is to find the number of good pairs. An ordered pair of integers (i, j) is said to be a good pair if it satisfies the following conditions:
1 ≤ i ≤ N
1 ≤ j ≤ M
(A_{i} \oplus B_{j}) < P
P divides ((A_{i} \cdot (A_{i} \oplus B_{j})) - 1)

where \oplus denotes the [bitwise XOR] operation.

Please help Chef and his friends, and find the number of good pairs.

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

- The first line of 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 three space-separated integers N, M, and P, respectively.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.
- The third line of each test case contains M space-separated integers B_{1}, B_{2}, \ldots, B_{M}.

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

For each test case, output one line containing a single integer — the number of good pairs.

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

$1 ≤ T ≤ 10^{3}$
$1 ≤ N, M ≤ 2 \cdot 10^{5}$
$2 ≤ A_{i}, B_{j} ≤ 10^{9}$ for every $1≤ i ≤ N$ and $1≤ j ≤ M$
$2 ≤ P ≤ 10^{9}$
$P$ is a prime number
- Sum of $N$ across all test cases will not exceed $2 \cdot 10^{5}$
- Sum of $M$ across all test cases will not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
3
2 2 17
7 14
2 13
1 1 11
2
2
4 3 101
10 91 99 200
81 182 149
----- Sample Output 1 ------ 
1
0
3

----- explanation 1 ------ 
Test Case $1$: There are $4$ ordered pairs of indices. Looking at them individually,
- $(1,1)$ is a good pair because $(7\oplus 2) = 5 < 17$, and $((7 \cdot (7 \oplus 2)) - 1) = 34$ is divisible by $17$.
- $(1, 2)$ is not a good pair because $((7 \cdot (7 \oplus 13)) - 1) = 69$ is not divisible by $17$.
- $(2, 1)$ is not a good pair because $((14 \cdot (14 \oplus 2)) - 1) = 167$ is not divisible by $17$.
- $(2, 2)$ is not a good pair because $((14 \cdot (14 \oplus 13)) - 1) = 41$ is not divisible by $17$.

Test Case $2$: The only ordered pair of indices is $(1, 1)$. This is not a good pair because $((2 \cdot (2 \oplus 2)) - 1) = -1$ is not divisible by $11$, since it leaves a remainder of $10$.

Difficulty: VERY_HARD
Tags: Number theory

Bit manipulation

Data structures

Mathematics
Skill types: Bit manipulation

Data structures

Starter code:

Solutions:
from collections import Counter
import sys
for _ in range(int(sys.stdin.readline())):
	(n, m, p) = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().strip().split()))
	b = list(map(int, sys.stdin.readline().strip().split()))
	d = Counter(b)
	c = 0
	for x in a:
		h = x ^ pow(x, p - 2, p)
		if x ^ h < p and x % p:
			c += d.get(h, 0)
	sys.stdout.write(str(c) + '\n')


for _ in range(int(input())):
	(n, m, p) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	xb = [[b[i], i] for i in range(m)]
	xb = sorted(xb)
	b = [xb[0][0], 1]
	for i in range(1, m):
		if xb[i][0] == xb[i - 1][0]:
			b[-1] += 1
		else:
			b += [xb[i][0], 1]
	b = {b[i]: b[i + 1] for i in range(0, len(b), 2)}
	ans = 0
	for i in range(n):
		if a[i] % p > 0:
			inv = pow(a[i], p - 2, p)
			temp = a[i] ^ inv
			ans += b.setdefault(temp, 0)
	print(ans)


import sys
tokens = ''.join(sys.stdin.readlines()).split()[::-1]

def next():
	return tokens.pop()

def nextInt():
	return int(next())

def nextFloat():
	return float(next())

def getIntArray(n):
	return [nextInt() for _ in range(n)]

def getFloatArray(n):
	return [nextFloat() for _ in range(n)]

def getStringArray(n):
	return [next() for _ in range(n)]
testcase = True

def solve(testcase=1):
	(N, M, P) = map(int, getIntArray(3))
	A = getIntArray(N)
	B = getIntArray(M)
	from collections import Counter
	counter = Counter(B)
	ans = 0
	for itr in A:
		b = pow(itr, P - 2, P) ^ itr
		if itr ^ b < P and itr % P:
			ans += counter.get(b, 0)
	print(ans)
	pass
if testcase is None:
	testcaseCount = 1
	while tokens:
		solve(testcaseCount)
		testcaseCount += 1
else:
	testcaseCount = nextInt() if testcase else 1
	for tc in range(testcaseCount):
		solve(tc + 1)
	assert not tokens


for tc in range(int(input())):
	ls = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	p = ls[-1]
	ct = 0
	dis = dict()
	for x in b:
		dis[x] = 1 if dis.get(x) is None else dis[x] + 1
	for x in a:
		if x % p:
			minv = pow(x, p - 2, p)
			if dis.get(minv ^ x) is not None:
				ct += dis[minv ^ x]
	print(ct)


from math import gcd
from collections import Counter
for i in range(int(input())):
	(n, m, p) = map(int, input().split())
	la = list(map(int, input().split()))
	lb = list(map(int, input().split()))
	l = []
	res = dict(Counter(lb))
	ans = 0
	for j in la:
		if gcd(j, p) != 1:
			continue
		y = pow(j, p - 2, p)
		x = y ^ j
		l.append(x)
	for j in l:
		ans += res.get(j, 0)
	print(ans)


from sys import stdin
input = stdin.readline

def answer():
	d = dict()
	for i in range(m):
		d[b[i]] = d.get(b[i], 0) + 1
	ans = 0
	for i in range(n):
		if a[i] % p == 0:
			continue
		x = pow(a[i], p - 2, p)
		ans += d.get(a[i] ^ x, 0)
	return ans
for T in range(int(input())):
	(n, m, p) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(answer())


def func():
	(n, m, p) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	dicti = {}
	for i in B:
		dicti[i] = dicti.get(i, 0) + 1
	ans = 0
	for ai in A:
		if ai % p != 0:
			modinv = pow(ai, p - 2, p)
			b = ai ^ modinv
			ans += dicti.get(b, 0)
	return ans
for _ in range(int(input())):
	print(func())