*Mario has reached Bowser's Castle and is inches away from rescuing Princess Peach. He has to answer the following problem at the gate to be allowed to enter. Can you help him?*

Let S(M) denote the set of all [prime] [factors] of M.  
Given two positive integers A and B, determine whether A is divisible by all elements in S(B).

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line of input, A and B, as mentioned in the statement.

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

For each test case, print YES if A is divisible by all elements in S(B) and NO otherwise. 

You may print each character of the string in uppercase or lowercase (for example, the strings YES, yEs, yes, and yeS will all be treated as identical).

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ A, B ≤ 10^{18}$

----- Sample Input 1 ------ 
3
21 63
72 72
25 20
----- Sample Output 1 ------ 
YES
YES
NO
----- explanation 1 ------ 
Test case $1$: The set of all prime factors of $B = 63$ is given by $S(B) = \{3, 7\}$. Also, $A = 21$ is divisible by all elements in $S(B)$.

Test case $2$: The set of all prime factors of $B = 72$ is given by $S(B) = \{2, 3\}$. Also, $A = 72$ is divisible by all elements in $S(B)$.

Test case $3$: The set of all prime factors of $B = 20$ is given by $S(B) = \{2, 5\}$. Here, $A = 25$ is not divisible by $2$ in $S(B)$.

Difficulty: HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
def gcd(x, y):
	if y == 0:
		return x
	if x >= y:
		return gcd(y, x % y)
	else:
		return gcd(x, y % x)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	while gcd(a, b) != 1:
		if a % b == 0:
			break
		b = b // gcd(a, b)
	if gcd(a, b) == 1 and a % b != 0:
		print('NO')
	else:
		print('YES')


from math import gcd
for _ in range(int(input())):
	(A, B) = map(int, input().split())
	gc = gcd(A, B)
	C = B
	while C != 1 and gc != 1:
		gc = gcd(A, B)
		C = B // gc
		A = gc
		B = C
	if C == 1:
		print('YES')
	else:
		print('NO')


import math
n = int(input())
for i in range(1, n + 1):
	(a, b) = map(int, input().split())
	c = 0
	d = pow(a, max(a, b), b)
	if d == 0:
		print('YES')
	else:
		print('NO')


import math
import bisect
for _ in range(int(input())):
	l = list(map(int, input().strip().split()))
	while l[1] != 1:
		gd = math.gcd(l[0], l[1])
		if gd == 1:
			break
		l[1] = l[1] // gd
	if l[1] == 1:
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	g = 0
	flag = 0
	while g != 1:
		g = gcd(a, b)
		b //= g
		if b == 1:
			flag = 1
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


import math
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	g = math.gcd(a, b)
	if g == b:
		print('YES')
	else:
		while b > 1:
			b = b // g
			g = math.gcd(a, b)
			if g == 1:
				break
		if b == 1:
			print('YES')
		else:
			print('NO')


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

def findGCD(lst, n):
	result = lst[0]
	for i in lst:
		result = gcd(result, i)
		if result == 1:
			return 1
	return result
t = int(input())
while t:
	t -= 1
	(a, b) = list(map(int, input().split()))
	g = 0
	flag = 0
	while g != 1:
		g = gcd(a, b)
		b //= g
		if b == 1:
			flag = 1
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


def gcd(n, m):
	if m == 0:
		return n
	else:
		return gcd(m, n % m)
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	if pow(a, 60, b) == 0:
		print('YES')
	else:
		print('NO')


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

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

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)

def isDivisible(x, y):
	if y == 1:
		return True
	z = gcd(x, y)
	if z == 1:
		return False
	return isDivisible(x, y // z)
for testcases in range(intin()):
	(x, y) = [int(x) for x in input().split()]
	flag = isDivisible(x, y)
	print('YES') if flag else print('NO')


import math
t = int(input())
while t:
	t -= 1
	(a, b) = map(int, input().split())
	gcd = math.gcd(a, b)
	for i in range(80):
		a = a * gcd % b
		if a == 0:
			print('YES')
			break
	else:
		print('NO')


from math import gcd
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	res = gcd(a, b)
	while res > 1:
		b //= res
		res = gcd(a, b)
	if b <= 1:
		print('YES')
	else:
		print('NO')


import math
inp = int(input())
for i in range(inp):
	(p, q) = map(int, input().split())
	while math.gcd(p, q) > 1:
		q = q // math.gcd(p, q)
	if q <= 1:
		print('YES')
	else:
		print('NO')


import sys
from math import gcd

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

def iinp():
	return int(inp())

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

def liinp():
	return list(mp())

def lmps():
	return list(map(str, inp()))

def solve(a, b):
	while gcd(a, b) > 1:
		b = b // gcd(a, b)
	if b <= 1:
		return 'YES'
	return 'NO'
tc = iinp()
for _ in range(tc):
	(a, b) = liinp()
	print(solve(a, b))


for i in range(int(input())):
	(a, b) = map(int, input().split())
	print('YES') if a ** 60 % b == 0 else print('NO')


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	print('YES' if pow(a, 59, b) == 0 else 'NO')


import math
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	f = 1
	while b != 1:
		sav = math.gcd(a, b)
		if sav == 1:
			f = 0
			print('NO')
			break
		b = b // sav
	if f == 1:
		print('YES')


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	print('NO' if pow(a, 60, b) else 'YES')


from math import gcd
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	while gcd(a, b) > 1:
		b //= gcd(a, b)
	if b <= 1:
		print('YES')
	else:
		print('NO')


import math
for tea in range(int(input())):
	(a, b) = map(int, input().split())
	g = math.gcd(a, b)
	while True:
		gg = math.gcd(g, b)
		if gg == 1:
			break
		if gg == g:
			b = b // g
		else:
			b = b // gg
	if b > 1:
		print('NO')
	else:
		print('YES')


import math
for tea in range(int(input())):
	(a, b) = map(int, input().split())
	g = math.gcd(a, b)
	while math.gcd(g, b) > 1:
		if b % g == 0:
			b = b // g
			continue
		y = math.gcd(b, g)
		b = b // y
	if b > 1:
		print('NO')
	else:
		print('YES')


import sys
import math
t = int(input())
for _ in range(t):
	(a, b) = [int(i) for i in sys.stdin.readline().split()]
	g = math.gcd(a, b)
	while g != 1:
		b = b // g
		g = math.gcd(b, g)
	if b == 1:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(a, b) = map(int, input().split())
	v = a ** 60
	if v % b == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(A, B) = map(int, input().split())
	print('YES' if pow(A, 60, B) == 0 else 'NO')


t = int(input())
for _ in range(t):
	(c, d) = map(int, input().split())
	print('YES' if pow(c, 60, d) == 0 else 'NO')


import math
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	while math.gcd(x, y) > 1:
		y //= math.gcd(x, y)
	if y <= 1:
		print('YES')
	else:
		print('NO')


import math

def isDivisible(a, b):
	if b == 1:
		return 'YES'
	x = math.gcd(a, b)
	if x == 1:
		return 'NO'
	return isDivisible(a, b // x)
t = int(input())
while t != 0:
	(a, b) = map(int, input().split(' '))
	print(isDivisible(a, b))
	t -= 1


def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	c = 0
	while c == 0:
		q = gcd(a, b)
		b = b // q
		if q == 1:
			if b != 1:
				print('NO')
				c = 1
		if b == 1:
			print('YES')
			c = 1


import math
for _ in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	d = 1
	while b != 1:
		g = math.gcd(a, b)
		if g == 1:
			d = 0
			break
		b = b // g
	if d == 1:
		print('YES')
	else:
		print('NO')


from collections import defaultdict
import math as mt
for _ in range(int(input())):
	(a, b) = (int(i) for i in input().split())
	while mt.gcd(a, b) != 1:
		b //= mt.gcd(a, b)
	if b != 1:
		print('NO')
	else:
		print('YES')


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	(a, b) = map(int, input().split(' '))
	while gcd(a, b) > 1:
		b = b // gcd(a, b)
	if b <= 1:
		print('YES')
	else:
		print('NO')


import math
n = int(input())
for u in range(n):
	(a, b) = map(int, input().split())
	while math.gcd(a, b) > 1:
		b //= math.gcd(a, b)
	if b <= 1:
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input())
for u in range(n):
	(num1, num2) = map(int, input().split())
	if num1 ** 59 % num2 == 0:
		print('YES')
	else:
		print('NO')


import math

def prime():
	(n, m) = map(int, input().split())

	def reducer(n, x):
		while True:
			x = math.gcd(n, x)
			if x == 1:
				break
			n //= x
		return n
	return reducer(m, math.gcd(n, m)) == 1
for _ in range(int(input())):
	print('YES' if prime() else 'NO')


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

def solve(A, B):
	while B != 1:
		g = gcd(A, B)
		if g == 1:
			return 'NO'
		B //= g
	return 'YES'
for _ in range(int(input())):
	(A, B) = map(int, input().split())
	print(solve(A, B))


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	while math.gcd(a, b) > 1:
		b = b // math.gcd(a, b)
	if b < 2:
		print('YES')
	else:
		print('NO')


def GCD(a, b):
	if b == 0:
		return abs(a)
	else:
		return GCD(b, a % b)
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	while GCD(a, b) > 1:
		b = b // GCD(a, b)
	if b > 1:
		print('NO')
	else:
		print('YES')


from math import gcd
test = int(input())
while test:
	(a, b) = map(int, input().split())
	while True:
		k = gcd(a, b)
		if k == 1:
			break
		else:
			b //= k
	if b == 1:
		print('YES')
	else:
		print('NO')
	test -= 1


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	while b != 1:
		g = math.gcd(a, b)
		if g == 1:
			print('NO')
			break
		b = b // g
	if b == 1:
		print('YES')


from math import gcd

def solve(a, b):
	if b == 1:
		return True
	g = gcd(a, b)
	aa = a // g
	bb = b // g
	if a == aa and b == bb:
		return False
	return solve(g, bb)
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	f = solve(a, b)
	if f:
		ans = 'YES'
	else:
		ans = 'NO'
	print(ans)