Your friend gives you an equation $A\equiv X^2\pmod{M}$ and asks you to find an integer solution for ${X}$.  

However, you know your friend's mischievous nature and suspect that there is no solution to such an equation. Thus, you first want to find out whether there is a solution to it.  

You may find this link helpful: http://mathworld.wolfram.com/EulersCriterion.html

Input Format

The first line contains the number of cases, ${T}$. ${T}$ lines follow, each containing two integers ${A}$ and ${M}$ separated by a single space.  

Constraints

${0}<T\leq10^5$  
$2\leq M<10^{9}$, ${M}$ is prime  
$0\leq A\lt M$

Output Format

Output ${T}$ lines, each containing one word: YES, if a solution exists and NO otherwise.  

Sample Input
2  
5 7  
4 7

Sample Output
NO  
YES

Explanation

In the second test case, we can take $X=2$, as $4\equiv2^2\pmod{7}$. Or we can take $X=5$, as $5^2=25\equiv4\pmod7$.  

However there is no integer which gives $5$ modulo $7$ when squared.

Difficulty: EASY
Tags: Number theory

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(a, p) = map(int, input().split())
	print('YES' if a == 0 or pow(a, (p - 1) // 2, p) == 1 else 'NO')


import sys

def legendre_symbol(a, p):
	ls = pow(a, p - 1 >> 1, p)
	return -1 if ls == p - 1 else ls

def modular_sqrt(a, p):
	if legendre_symbol(a, p) != 1:
		return 0
	elif a == 0:
		return 0
	elif p == 2:
		return 1
	elif p % 4 == 3:
		return 1
	return 1

def solve():
	stdin = sys.stdin
	write = sys.stdout.write
	t = int(stdin.readline())
	for _ in range(t):
		(a, b) = map(int, stdin.readline().split())
		if a == 0:
			print('YES')
		else:
			print('YES' if modular_sqrt(a, b) else 'NO')
solve()


for t in range(int(input())):
	(a, m) = [int(i) for i in input().split()]
	if m == 2 or a == 0:
		print('YES')
		continue
	if pow(a, (m - 1) // 2, m) == 1:
		print('YES')
	else:
		print('NO')


T = int(input())
for t in range(T):
	(A, M) = input().split()
	M = int(M)
	A = int(A)
	if M > 2:
		res = pow(A, int((M - 1) / 2), M)
		if res == 1 or res == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	(a, m) = [int(x) for x in input().split()]
	if m == 2:
		if a == 0 or a == 1:
			print('YES')
		else:
			print('NO')
	elif a == 0:
		print('YES')
	elif pow(a, (m - 1) // 2, m) == 1:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(A, M) = map(int, input().split())
	if A == 0 or M == 2:
		print('YES')
		continue
	print('YES' if pow(A, (M - 1) // 2, M) == 1 else 'NO')


import sys

def modPow(a, p, m):
	if p == 1:
		return a
	else:
		a = a % m
		r = 1
		if p % 2 == 1:
			r = a
			p -= 1
		return r * modPow(a * a % m, p / 2, m)
data = sys.stdin.readlines()
cases = int(data[0])
for line in data[1:]:
	[A, M] = line.rstrip().split(' ')
	A = int(A)
	M = int(M)
	if A == 0:
		print('YES')
	elif M == 2:
		print('YES')
	else:
		x = modPow(A, (M - 1) / 2, M) % M
		if x == 1:
			print('YES')
		else:
			print('NO')


def is_perfect_square(A, M):
	if M == 2 or A == 0:
		return True
	else:
		exponent = (M - 1) // 2
		result = 1
		current_power_of_A = A
		while exponent > 0:
			if exponent % 2 == 1:
				result = result * current_power_of_A
				result = result % M
			exponent = exponent // 2
			current_power_of_A = current_power_of_A * current_power_of_A
			current_power_of_A = current_power_of_A % M
		return result == 1
num_test_cases = int(input())
for c in range(num_test_cases):
	line = input().split()
	A = int(line[0])
	M = int(line[1])
	if is_perfect_square(A, M):
		print('YES')
	else:
		print('NO')


from sys import *

def modpow(a, b, c):
	if b == 1:
		return a % c
	ne = b // 2
	k = modpow(a, ne, c)
	if b % 2 == 0:
		return k * k % c
	return k * k * a % c
t = int(stdin.readline())
for i in range(t):
	[A, M] = [int(i) for i in stdin.readline().split()]
	if A < 2 or M == 2:
		print('YES')
	elif modpow(A, (M - 1) // 2, M) == 1:
		print('YES')
	else:
		print('NO')


from fractions import gcd
t = int(input())
for i in range(0, t):
	ip = input().split(' ')
	a = int(ip[0])
	m = int(ip[1])
	if a == 0:
		print('YES')
	elif m == 2 or gcd(a, m) != 1:
		print('NO')
	else:
		cal = pow(a, int((m - 1) / 2), m)
		if (cal + 1) % m == 0:
			print('NO')
		else:
			print('YES')


t = int(input())
for _ in range(t):
	(a, m) = input().split()
	a = int(a)
	m = int(m)
	x = -1 % m
	y = int((m - 1) / 2)
	ans = pow(a, y, m)
	if m == 2:
		print('YES')
	elif ans == x:
		print('NO')
	else:
		print('YES')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(A, M) = list(map(int, sys.stdin.readline().split()))
	if M == 2:
		print('YES')
	else:
		print('NO' if pow(A, (M - 1) // 2, M) == M - 1 else 'YES')


def solve(A, M):
	if A == 0 or M == 2:
		return True
	if pow(A, (M - 1) // 2, M) == 1:
		return True
	else:
		return False
T = int(input())
for _ in range(T):
	(A, M) = (int(_) for _ in input().split())
	if solve(A, M):
		print('YES')
	else:
		print('NO')


def is_square_modulo(a, m):
	return a == 0 or pow(a, (m - 1) // 2, m) == 1
for _ in range(int(input())):
	(a, m) = map(int, input().split())
	if is_square_modulo(a, m):
		print('YES')
	else:
		print('NO')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(A, M) = list(map(int, sys.stdin.readline().split()))
	if M == 2:
		print('YES')
	else:
		print('NO' if pow(A, (M - 1) // 2, M) == M - 1 else 'YES')


for _ in range(int(input())):
	(A, M) = [int(x) for x in input().split()]
	if A == 0:
		print('YES')
	elif pow(A, (M - 1) // 2, M) == 1:
		print('YES')
	else:
		print('NO')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(A, M) = list(map(int, sys.stdin.readline().split()))
	if M == 2:
		print('YES')
	else:
		print('NO' if pow(A, (M - 1) // 2, M) == M - 1 else 'YES')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(A, M) = list(map(int, sys.stdin.readline().split()))
	if M == 2:
		print('YES')
	else:
		print('NO' if pow(A, (M - 1) // 2, M) == M - 1 else 'YES')


for t in range(int(input())):
	(a, m) = map(int, input().split())
	if a == 0:
		print('YES')
		continue
	print('YES' if pow(a, m // 2, m) == 1 else 'NO')


def mpow(b, e, m):
	result = 1
	b = b % m
	while e > 0:
		if e % 2 == 1:
			result = result * b % m
		e = e >> 1
		b = b * b % m
	return result
T = int(input())
for _ in range(T):
	(A, M) = [int(i) for i in input().split()]
	print('YES' if A == 0 or mpow(A, (M - 1) // 2, M) == 1 else 'NO')


def is_quadratic_residue(num, modulo):
	res = pow(num, (modulo - 1) // 2, modulo)
	return 'YES' if res == 1 or num == 0 else 'NO'
for _ in range(int(input())):
	(num, modulo) = [int(x) for x in input().split()]
	print(is_quadratic_residue(num, modulo))


for _ in range(int(input())):
	(a, m) = input().split()
	exp = int((int(m) - 1) / 2)
	if pow(int(a), exp, int(m)) == 1 or int(a) == 0:
		print('YES')
	else:
		print('NO')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(A, M) = list(map(int, sys.stdin.readline().split()))
	if M == 2:
		print('YES')
	else:
		print('NO' if pow(A, (M - 1) // 2, M) == M - 1 else 'YES')


T = int(input())
for _ in range(T):
	(A, M) = (int(x) for x in input().split())
	print('YES') if pow(A, (M - 1) // 2, M) == 1 or A == 0 else print('NO')


def modPow(x, y, m):
	if y == 0:
		return 1
	if y == 1:
		return x
	temp = modPow(x, y // 2, m)
	if y % 2 == 0:
		return temp * temp % m
	else:
		return temp * temp % m * x % m
t = int(input())
for _ in range(t):
	(a, m) = list(map(int, input().split()))
	if modPow(a, (m - 1) // 2, m) == 1 or (m == 2 and a % 2 == 1) or a == 0:
		print('YES')
	else:
		print('NO')


from fileinput import input

def find():
	lines = input()
	noc = [int(x) for x in lines[0].strip().split()][0]
	for i in range(1, noc + 1):
		(a, m) = [int(x) for x in lines[i].strip().split()]
		if m == 2 or a == 0:
			print('YES', end='\n')
			continue
		n = (m - 1) // 2
		if (check(a, n, m) - 1) % m == 0:
			print('YES', end='\n')
		else:
			print('NO', end='\n')

def check(a, n, m):
	if n == 1:
		return a % m
	half = check(a, n // 2, m)
	tmp = half * half % m
	if n % 2 == 0:
		return tmp
	else:
		return tmp * (a % m) % m
find()


import math

def euler_cri(a, m):
	if a == 0 or m == 2:
		print('YES')
	elif pow(a, (m - 1) // 2, m) == 1:
		print('YES')
	else:
		print('NO')
for i in range(int(input())):
	(a, m) = input().split()
	(a, m) = (int(a), int(m))
	euler_cri(a, m)


def legendre_symbol(a, p):
	ls = pow(a, (p - 1) // 2, p)
	return -1 if ls == p - 1 else ls
for _ in range(int(input())):
	(A, M) = [int(ns) for ns in input().split()]
	if A == 0:
		print('YES')
	elif M == 2:
		print('YES')
	elif legendre_symbol(A, M) != -1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(a, m) = input().split()
	(a, m) = (int(a), int(m))
	if a == 0 or m == 2 or pow(a, (m - 1) // 2, m) == 1:
		print('YES')
	else:
		print('NO')


import math
import string

def func(n, k):
	i = int((k - 1) / 2)
	ans = 1
	j = n
	while i:
		if i & 1 == 1:
			ans = ans * j % k
		j = j * j % k
		i >>= 1
	return ans
t = int(input())
for i in range(0, t):
	(n, k) = [int(x) for x in input().split()]
	n = n % k
	if k == 2:
		print('YES')
	else:
		j = func(n, k)
		if j == 1:
			print('YES')
		elif j == 0:
			print('YES')
		else:
			print('NO')


def doesSolutionExist(a, m):
	if a == 0:
		return 'YES'
	elif pow(a, (m - 1) // 2, m) == 1:
		return 'YES'
	else:
		return 'NO'

def main():
	t = int(input())
	for _ in range(t):
		(a, m) = list(map(int, input().split()))
		print(doesSolutionExist(a, m))
main()


import math
T = int(input())
for i in range(0, T):
	(a, b) = map(int, input().split())
	if a == 0:
		print('YES')
	else:
		k = pow(a, int((b - 1) / 2), b)
		if k == 1:
			print('YES')
		else:
			print('NO')


def jacobi(a, n):
	if n == 2:
		return 1
	if a == 0:
		return 1
	num = a % n
	den = n
	sign = 1
	while num >= 2:
		while num % 4 == 0:
			num //= 4
		if num % 2 == 0:
			x = den % 8
			if x == 3 or x == 5:
				sign = -1 * sign
			num //= 2
		if num == 1:
			break
		if num % 4 == 3 and den % 4 == 3:
			sign = -1 * sign
		(num, den) = (den % num, num)
	return sign * num
T = int(input())
while T:
	X = [int(i) for i in input().split()]
	a = jacobi(X[0], X[1])
	if a == 1:
		print('YES')
	else:
		print('NO')
	T -= 1


t = int(input())
for i in range(t):
	inp = list(input().split(' '))
	a = int(inp[0])
	m = int(inp[1])
	x = pow(a, (m - 1) // 2, m)
	if x == 1 or a == 0:
		print('YES')
	else:
		print('NO')


from functools import reduce
for _ in range(int(input())):
	(a, p) = map(int, input().split())
	exponent = '{0:b}'.format((p - 1) // 2)
	n_powers = len(exponent)
	power_table = [a] * n_powers
	for i in range(1, n_powers):
		power_table[i] = power_table[i - 1] ** 2 % p
	result = reduce(lambda a, b: a * b % p, [power_table[i] for i in range(n_powers) if exponent[n_powers - i - 1] == '1'], 1)
	print('YES' if result == 1 or a == 0 else 'NO')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(A, M) = list(map(int, sys.stdin.readline().split()))
	if M == 2:
		print('YES')
	else:
		print('NO' if pow(A, (M - 1) // 2, M) == M - 1 else 'YES')


for T in range(int(input())):
	(A, M) = list(map(int, input().split()))
	check = pow(A, (M - 1) // 2, M)
	if check == 1 or check == 0:
		print('YES')
	else:
		print('NO')


T = int(input())

def successiveSquares(a, ex, p):
	decomp = bin(ex)
	s = [a]
	for _ in range(1, len(decomp) - 2):
		s.append(s[-1] ** 2 % p)
	answer = 1
	for (i, b) in enumerate(decomp[:1:-1]):
		if b == '1':
			answer *= s[i]
	answer = answer % p
	return answer

def euler(a, p):
	if a == 0:
		return 1
	x = int((p - 1) / 2)
	c = successiveSquares(a, x, p)
	return c
for t in range(T):
	(A, M) = [int(x) for x in input().split()]
	if euler(A, M) == 1:
		print('YES')
	else:
		print('NO')


def expmod_iter(a, b, c):
	x = 1
	while b > 0:
		if b & 1 == 1:
			x = x * a % c
		a = a * a % c
		b >>= 1
	return x % c
for _ in range(int(input())):
	(a, m) = map(int, input().split())
	if m == 2 or a == 0 or expmod_iter(a, m // 2, m) == 1:
		print('YES')
	else:
		print('NO')


def po_mo(kake, kai, hou):
	if kai == 0:
		return 1
	else:
		return po_mo(kake, kai // 2, hou) ** 2 * (1 if kai % 2 == 0 else kake) % hou
Tasks = int(input())
for idx in range(0, Tasks, 1):
	mojir = input()
	hyo = mojir.split(' ')
	A = int(hyo[0])
	P = int(hyo[1])
	if P == 2:
		print('YES')
	elif po_mo(A, (P - 1) // 2, P) != P - 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(a, p) = list(map(int, input().split()))
	if a == 0:
		print('YES')
	else:
		print('YES' if pow(a, (p - 1) // 2, p) == 1 else 'NO')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(A, M) = list(map(int, sys.stdin.readline().split()))
	if M == 2:
		print('YES')
	else:
		print('NO' if pow(A, (M - 1) // 2, M) == M - 1 else 'YES')


def euler_crit(aa, mm):
	n1 = (mm - 1) // 2
	x = aa % mm
	for i1 in range(n1 - 1):
		x = x * (aa % mm) % mm
	return x

def euler_crit1(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	else:
		if n % 2 == 0:
			return euler_crit1(a * a % m, n / 2, m)
		if n % 2 == 1:
			return a * euler_crit1(a * a % m, (n - 1) / 2, m) % m
nTst = int(input())
inp = []
for i1 in range(nTst):
	inp.append(list(map(int, input().split())))
for i1 in range(nTst):
	a1 = inp[i1][0]
	m1 = inp[i1][1]
	n1 = (m1 - 1) // 2
	ec = euler_crit1(a1, n1, m1)
	if (ec == 1) | (ec == 0):
		print('YES')
	else:
		print('NO')


def test_case():
	(a, m) = [int(x) for x in input().split()]
	if a == 0 or m == 2:
		print('YES')
	elif pow(a, (m - 1) // 2, m) == 1:
		print('YES')
	else:
		print('NO')

def main():
	T = int(input())
	while T > 0:
		test_case()
		T -= 1
main()


t = int(input())
for _ in range(t):
	(a, m) = map(int, input().split())
	if a == 0 or pow(a, (m - 1) // 2, m) == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	a = input()
	i = a.find(' ')
	b = int(a[0:i])
	x = int(a[i + 1:])
	n = int((x - 1) / 2)
	q = int(pow(b, n, x))
	if b == 0:
		print('YES')
	elif q == 1:
		print('YES')
	else:
		print('NO')
	t = t - 1


t = int(input())
for _ in range(t):
	(a, n) = (int(x) for x in input().split())
	print('YES') if a == 0 or pow(a, n >> 1, n) == 1 else print('NO')


t = int(input())
for count in range(t):
	(a, m) = input().split()
	a = int(a)
	m = int(m)
	l = [0 for i in range(35)]
	li = [0 for i in range(35)]
	l[0] = a
	x = m // 2
	li[0] = x % 2
	x = x // 2
	p = 1
	for i in range(1, 35):
		l[i] = l[i - 1] * l[i - 1] % m
		li[i] = x % 2
		x = x // 2
	for i in range(35):
		if li[i] == 1:
			p = p * l[i] % m
	if a == 0:
		print('YES')
	elif p == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(a, p) = map(int, input().split())
	print('YES' if a == 0 or pow(a, (p - 1) // 2, p) == 1 else 'NO')


n = input().strip()
a = []
for a_i in range(int(n)):
	a_t = [int(a_temp) for a_temp in input().strip().split(' ')]
	a.append(a_t)
for i in range(0, int(n)):
	an = a[i][0]
	p = a[i][1]
	exp = int((p - 1) / 2)
	flag = pow(an, exp, p)
	if flag == 1:
		print('YES')
	elif flag == p - 1:
		print('NO')
	else:
		print('YES')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(A, M) = list(map(int, sys.stdin.readline().split()))
	if M == 2:
		print('YES')
	else:
		print('NO' if pow(A, (M - 1) // 2, M) == M - 1 else 'YES')


t = int(input())
for a0 in range(0, t):
	(a, p) = map(int, input().split())
	if a == 0 or p == 2 or pow(a, int((p - 1) / 2), p) == 1:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	(A, M) = map(int, input().split())
	exp = (M - 1) // 2
	r = pow(A, exp, M)
	if A == 0 or r == 1:
		print('YES')
	else:
		print('NO')


def modpow(a, b, m):
	acc = 1
	curpow = a
	while b > 0:
		if b & 1:
			acc = acc * curpow % m
		curpow = curpow ** 2 % m
		b >>= 1
	return acc
for _ in range(int(input())):
	(A, M) = map(int, input().strip().split())
	if M == 2 or A == 0:
		print('YES')
	else:
		mp = modpow(A, (M - 1) // 2, M)
		print('YES' if mp == 1 else 'NO')


for _ in range(int(input())):
	(A, M) = map(int, input().split())
	if M == 2:
		print('YES')
	else:
		print('NO' if pow(A, (M - 1) // 2, M) == M - 1 else 'YES')


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print('YES' if b == 2 or a == 0 or pow(a, (b - 1) // 2, b) == 1 else 'NO')


import sys
numline = -1
for line in sys.stdin:
	if numline == -1:
		numline = int(line)
	else:
		line = line.split(' ')
		var = pow(int(line[0]), int((int(line[1]) - 1) / 2), int(line[1]))
		if var == 1 or var == 0:
			print('YES')
		else:
			print('NO')


import sys

def criteria(A, M):
	if M == 2:
		return 'YES'
	if A == 0:
		return 'YES'
	return 'YES' if pow(A, (M - 1) // 2, M) == 1 else 'NO'
for line in sys.stdin.readlines()[1:]:
	stuff = list(map(int, line.split()))
	(A, M) = (stuff[0], stuff[1])
	print(criteria(A, M))


numCases = int(input())
for iCase in range(numCases):
	splitInput = input().split()
	A = int(splitInput[0])
	M = int(splitInput[1])
	if M != 2 and A != 0:
		powerToRaise = M // 2
		value = pow(A, powerToRaise, M)
		print('YES' if value == 1 else 'NO')
	else:
		print('YES')


t = int(input())

def exp(n, x, m):
	if x == 1:
		return n % m
	elif x == 0:
		return 1
	elif x % 2 == 0:
		return exp(n * n % m, x / 2, m)
	elif x % 2 == 1:
		return n * exp(n * n % m, (x - 1) / 2, m) % m
for i in range(t):
	(a, m) = map(int, input().split())
	if a == 0:
		print('YES')
	elif m == 2:
		print('YES')
	else:
		ans = exp(a, (m - 1) // 2, m)
		ans = ans % m
		if ans == 1:
			print('YES')
		else:
			print('NO')


def qr(a, m):
	return a == 0 or 1 == pow(a, m - 1 >> 1, m)
for _ in range(int(input().strip())):
	(a, m) = map(int, input().strip().split())
	print('YES' if qr(a, m) else 'NO')


t = int(input())

def pwrMod(a, k, mod):
	if k == 0:
		return 1
	h = pwrMod(a, k // 2, mod)
	h *= h
	if k % 2 == 1:
		h *= a
	return h % mod
for k in range(t):
	(a, m) = input().strip().split(' ')
	(a, m) = (int(a), int(m))
	if m == 2 or a == 0:
		print('YES')
	else:
		print('YES' if pwrMod(a, (m - 1) // 2, m) == 1 else 'NO')


import sys
t = int(input())
for _ in range(t):
	(a, m) = [int(x) for x in input().split()]
	print('YES' if pow(a, int((m - 1) / 2), m) == 1 or a == 0 else 'NO')


import sys, math

def eulers_criterion(A, M):
	if A == 0:
		return True
	exponent = (M - 1) // 2
	result = 1
	base = A % M
	while exponent > 0:
		if exponent % 2 == 1:
			result = result * base % M
		exponent = exponent >> 1
		base = base * base % M
	return result % M == 1

def main():
	T = int(input())
	lines = [[int(b) for b in x.strip().split()] for x in sys.stdin.readlines()]
	for line in lines:
		print('YES' if eulers_criterion(*line[:2]) else 'NO')
main()


def exponentiate(a, p, m):
	if p == 0:
		return 1
	elif p == 1:
		return a
	else:
		return a ** (p & 1) * exponentiate(a * a % m, p // 2, m) % m

def sqrtable(a, m):
	return a == 0 or abs(exponentiate(a, (m - 1) // 2, m)) == 1
T = int(input())
for i in range(T):
	print('YES' if sqrtable(*(int(x) for x in input().split())) else 'NO')


def power_mod(number, power, prime):
	if power == 1:
		return number % prime
	half = power_mod(number, power // 2, prime)
	res = half * half % prime
	if power % 2:
		res *= number
		res %= prime
	return res

def euler_criterion(number, prime):
	return power_mod(number, (prime - 1) // 2, prime)

def is_quadratic_residue_mod_prime(number, prime):
	if prime == 2 or number == 0 or number == 1:
		return True
	return euler_criterion(number, prime) == 1
T = int(input())
for _ in range(T):
	(a, m) = map(int, input().strip().split())
	print('YES' if is_quadratic_residue_mod_prime(a, m) else 'NO')


t = int(input())
for i in range(0, t):
	s = [int(x) for x in input().split()]
	(a, m) = (s[0], s[1])
	if m == 2:
		print('YES')
	else:
		check = pow(a, (m - 1) // 2, m) == m - 1
		if check:
			print('NO')
		else:
			print('YES')


def power(a, e, m):
	if e == 1:
		return a
	else:
		s = power(a, e // 2, m)
		s = s * s % m
		if e % 2 == 1:
			s = s * a % m
		return s
t = int(input())
for i in range(t):
	(a, m) = map(int, input().split())
	if m == 2:
		print('YES')
	else:
		e = (m - 1) // 2
		p = power(a, e, m)
		if p in (0, 1):
			print('YES')
		else:
			print('NO')


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(A, M) = list(map(int, sys.stdin.readline().split()))
	if M == 2:
		print('YES')
	else:
		print('NO' if pow(A, (M - 1) // 2, M) == M - 1 else 'YES')


def read_ints():
	return [int(x) for x in input().strip().split(' ')]

def read_int():
	v = read_ints()
	return v[0]
T = read_int()
for t in range(T):
	(A, M) = read_ints()
	v = pow(A, (M - 1) // 2, M)
	if A == 0 or v == 1:
		print('YES')
	else:
		print('NO')


import math

def pow(base, exp, mod):
	base = base % mod
	result = 1
	while exp > 0:
		if exp % 2 == 1:
			result = result * base % mod
		base = base * base % mod
		exp = int(exp / 2)
	return result
n = int(input().strip())
for _ in range(n):
	(a, m) = [int(a) for a in input().strip().split()]
	p = (m - 1) / 2
	criterion = pow(a, p, m)
	if criterion == 1 or a == 1 or m == 1 or (a == 0):
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(a, m) = map(int, input().split())
	if a == 0 or m == 2 or pow(a, (m - 1) // 2, m) == 1:
		print('YES')
	else:
		print('NO')


import sys

def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	while b:
		(a, b) = (b, a % b)
	return a

def solve(a, m):
	g = gcd(a, m)
	print('a=%d b=%d g=%d' % (a, m, g), file=sys.stderr)
	if m == 2:
		return True
	if a == 0:
		return True
	v = pow(a, (m - 1) // 2, m)
	return v == 1
t = int(input())
for _ in range(t):
	(a, m) = map(int, input().split())
	if solve(a, m):
		print('YES')
	else:
		print('NO')


def modpow(base_value, exponent, modulus):
	base_value = base_value % modulus
	result = 1
	while exponent > 0:
		if exponent % 2 == 1:
			result = result * base_value % modulus
		base_value = base_value * base_value % modulus
		exponent = exponent // 2
	return result
t = int(input().strip())
for _ in range(t):
	(a, m) = map(int, input().strip().split())
	if 0 <= a <= 1 or m == 2:
		print('YES')
	else:
		print('YES' if modpow(a, (m - 1) // 2, m) == 1 else 'NO')


for _ in range(int(input())):
	(a, m) = map(int, input().split())
	if m == 2:
		print('YES')
	elif pow(a, (m - 1) // 2, m) == m - 1:
		print('NO')
	else:
		print('YES')


print('\n'.join(map(lambda x, p: 'YES' if p == 2 or pow(x, (p - 1) // 2, p) != p - 1 else 'NO', *zip(*(map(int, input().split()) for _ in range(int(input())))))))


def APow2Modulus(A, M, exp):
	if exp == 0:
		return 1
	while exp > 1:
		A = A * A % M
		exp >>= 1
	return A

def eulerCriterion(A, M):
	exp = M - 1 >> 1
	if M == 2 or A == 0 or A == 1:
		return True
	if exp == 1 and A != 1:
		return False
	modSum = 1
	e = 1
	while exp > 0:
		currBit = exp & 1
		if currBit == 1:
			pow2Mod = APow2Modulus(A, M, e)
			modSum *= pow2Mod
			modSum %= M
		e <<= 1
		exp >>= 1
	if modSum != 1:
		return False
	return True

def main():
	T = int(input().strip())
	for i in range(T):
		line = input().strip().split()
		A = int(line[0])
		M = int(line[1])
		if eulerCriterion(A, M):
			print('YES')
		else:
			print('NO')
main()


print('\n'.join(map(lambda x, p: 'YES' if p == 2 or pow(x, (p - 1) // 2, p) != p - 1 else 'NO', *zip(*(map(int, input().split()) for _ in range(int(input())))))))


n = int(input().strip())
for i in range(n):
	(a, p) = list(map(int, input().strip().split()))
	modulo = pow(a, (p - 1) // 2, p)
	if modulo == 1 or p == 2 or a == 0:
		print('YES')
	else:
		print('NO')


print('\n'.join(map(lambda x, p: 'YES' if p == 2 or pow(x, (p - 1) // 2, p) != p - 1 else 'NO', *zip(*(map(int, input().split()) for _ in range(int(input())))))))


print('\n'.join(map(lambda x, p: 'YES' if p == 2 or pow(x, (p - 1) // 2, p) != p - 1 else 'NO', *zip(*(map(int, input().split()) for _ in range(int(input())))))))


print('\n'.join(map(lambda x, p: 'YES' if p == 2 or pow(x, (p - 1) // 2, p) != p - 1 else 'NO', *zip(*(map(int, input().split()) for _ in range(int(input())))))))


print('\n'.join(map(lambda x, p: 'YES' if p == 2 or pow(x, (p - 1) // 2, p) != p - 1 else 'NO', *zip(*(map(int, input().split()) for _ in range(int(input())))))))


print('\n'.join(map(lambda x, p: 'YES' if p == 2 or pow(x, (p - 1) // 2, p) != p - 1 else 'NO', *zip(*(map(int, input().split()) for _ in range(int(input())))))))


print('\n'.join(map(lambda x, p: 'YES' if p == 2 or pow(x, (p - 1) // 2, p) != p - 1 else 'NO', *zip(*(map(int, input().split()) for _ in range(int(input())))))))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(A, M) = list(map(int, sys.stdin.readline().split()))
	if M == 2:
		print('YES')
	else:
		print('NO' if pow(A, (M - 1) // 2, M) == M - 1 else 'YES')


def legendre(a, p):
	result = pow(a, (p - 1) // 2, p)
	if result > 1:
		return -1
	return result
for i in range(int(input())):
	(a, p) = map(int, input().split())
	print(['YES', 'YES', 'NO'][legendre(a, p)])


print('\n'.join(map(lambda x, p: 'YES' if p == 2 or pow(x, (p - 1) // 2, p) != p - 1 else 'NO', *zip(*(map(int, input().split()) for _ in range(int(input())))))))


t = int(input().strip())

def calc_exponent(a, e, m):
	b = '{0:b}'.format(e)
	r = 1
	for (i, b) in enumerate(reversed(b)):
		if b != '0':
			r = r * calc_exp2(a, 2 ** i, m) % m
	return r

def calc_exp2(a, e, m):
	r = a
	while e != 1:
		r = r * r % m
		e = e / 2
	return r
for _ in range(t):
	(a, m) = [int(i) for i in input().strip().split()]
	if m == 2 or a == 0:
		print('YES')
		continue
	e = int((m - 1) / 2)
	r = calc_exponent(a, e, m)
	if r == 1:
		print('YES')
	else:
		print('NO')


print('\n'.join(map(lambda x, p: 'YES' if p == 2 or pow(x, (p - 1) // 2, p) != p - 1 else 'NO', *zip(*(map(int, input().split()) for _ in range(int(input())))))))