Chef calls a pair of integers (A, B) *equivalent* if there exist some positive integers X and Y such that A^{X} = B^{Y}.

Given A and B, determine whether the pair is *equivalent* or not.

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

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

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

For each test case, output YES if (A, B) is an *equivalent* pair, NO otherwise.

The output is case-insensitive. Thus, the strings Yes, YES, yes, and yeS are all considered identical.

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

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

----- Sample Input 1 ------ 
3
2 3
8 4
12 24

----- Sample Output 1 ------ 
NO
YES
NO

----- explanation 1 ------ 
Test case $1$: There are no positive integers $X$ and $Y$ which satisfy $A^{X} = B^{Y}$.

Test case $2$: Let $X = 2$ and $Y = 3$. Thus, $A^{X} = 8^{2} = 64$ and $B^{Y} = 4^{3} = 64$. Thus, the pair $(8, 4)$ is *equivalent*.

Test case $3$: There are no positive integers $X$ and $Y$ which satisfy $A^{X} = B^{Y}$.

Difficulty: HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
import math
for _ in range(int(input())):
	(a, b) = map(int, input().split(' '))
	(c, d) = (a, b)
	for i in range(40):
		if c == d:
			break
		elif c < d:
			c *= a
		else:
			d *= b
	if c != d:
		print('NO')
	else:
		print('YES')


test_case = int(input())
for i in range(test_case):
	(a, b) = map(int, input().split())
	maxi = max(a, b)
	mini = min(a, b)
	l = []
	ok = False
	for j in range(1, 20):
		l.append(maxi ** j)
		if mini ** j in l:
			ok = True
			break
	if ok:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(A, B) = map(int, input().split())
	maximum = max(A, B)
	minimum = min(A, B)
	l = []
	ans = 0
	for j in range(1, 40):
		l.append(maximum ** j)
		if minimum ** j in l:
			ans = 1
			break
	if ans == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	k = 0
	while k == 0:
		k = max(a, b) % min(a, b)
		q = max(a, b) / min(a, b)
		(a, b) = (q, min(a, b))
		if q == 1:
			break
	if q == 1:
		print('YES')
	else:
		print('NO')


from sys import stdin, stdout
_r = range
_l = len
_s = str
_i = int
_f = float
_m = map
_li = list
In = stdin.readline
Out = stdout.write
R = lambda : In().strip()
RS = lambda : R().split()
I = lambda : _i(R())
M = lambda : _m(_i, RS())
L = lambda : _li(_m(_i, RS()))
Nsum = lambda n: n * (n + 1) // 2
Det = lambda a, b, c: (-b + (b * b - 4 * a * c) ** 0.5) / 2
iBit = lambda n, i: n >> i & 1
Div2 = lambda x: x & ~(x - 1)
pow2 = lambda x: log(Div2(x), 2)
lcm = lambda x, y: x * y // gcd(x, y)
mode = lambda counter: counter.most_common(1)

def Y():
	stdout.write('Yes')

def N():
	stdout.write('No')
mod = 1000000007

def Mapp(arr):
	d = _dd(int)
	for i in arr:
		d[i] += 1
	return d

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

def isPrime(n):
	if n < 3:
		return n == 2
	for i in range(3, n, 2):
		if n % i == 0:
			return False
	return True

def Pow(a, b, mod):
	res = 1
	while b:
		if b & 1:
			res = res * a % mod
		a *= a
		b >>= 1
	return res

def nCr(n, r):
	x = y = 1
	if n - r < r:
		r = n - r
	while r:
		x *= n
		y *= r
		g = gcd(x, y)
		x //= g
		y //= g
		n -= 1
		r -= 1
	return x

def Countarr(li, n):
	arr = []
	i = 0
	mx = 0
	c = li[0]
	cnt = 0
	while i < n:
		if c == li[i]:
			cnt += 1
		else:
			mx = max(mx, cnt)
			arr.append(cnt)
			cnt = 1
			c = li[i]
		i += 1
	mx = max(mx, cnt)
	arr.append(cnt)
	return (C(arr), mx)

def LIS(arr, n):
	store = [0] * n
	p = 1
	store[0] = arr[0]
	for i in arr:
		if i > store[p - 1]:
			store[p] = i
			p += 1
		else:
			store[bL(store, i, 0, p - 1)] = i
	return p
mod = 998244353

def fun(x, d):
	c = 0
	while x % d == 0:
		c += 1
		x //= d
	return [c, x]
arr = []
mx = 10 ** 3
pr = [True] * (mx + 1)
for i in _r(2, mx + 1):
	if pr[i]:
		arr.append(i)
		j = i * i
		while j <= mx:
			pr[j] = False
			j += i

def solve():
	(a, b) = M()
	if a < b:
		(a, b) = (b, a)
	x = y = -1
	for i in arr:
		if a == 1 or b == 1:
			break
		(c1, a) = fun(a, i)
		(c2, b) = fun(b, i)
		if c1 and (not c2) or (c2 and (not c1)):
			return False
		g = gcd(c1, c2)
		if g == 0:
			continue
		if y == -1:
			x = c1 // g
			y = c2 // g
		elif x != c1 // g or y != c2 // g:
			return False
	return a == b
for _ in _r(I()):
	print('YES' if solve() else 'NO')


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	mx = max(a, b)
	mn = min(a, b)
	l2 = []
	count = 0
	for j in range(1, 20):
		l2.append(mx ** j)
		if mn ** j in l2:
			count = 1
			break
	if count == 1:
		print('YES')
	else:
		print('NO')


def solve():
	(a, b) = map(int, input().split())
	while a != b:
		mx = max(a, b)
		mn = min(a, b)
		if mx % mn != 0:
			print('NO')
			return
		(a, b) = (mn, mx // mn)
	print('YES')
t = int(input())
for _ in range(t):
	solve()


def gcd():
	(a, b) = map(int, input().split())
	while a != b:
		m = max(a, b)
		n = min(a, b)
		if m % n != 0:
			print('NO')
			return
		(a, b) = (n, m // n)
	print('YES')
case = int(input())
for _ in range(case):
	gcd()


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


from sys import stdin
input = stdin.readline

def fun(n, m):
	if n == m:
		return True
	if n < m:
		(n, m) = (m, n)
	if m == 1 and n == 1:
		return True
	if n % m:
		return False
	return fun(m, n // m)
for i in range(int(input())):
	(n, m) = map(int, input().split())
	print('YES' if fun(n, m) else 'NO')


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = set()
	d = set()
	for i in range(1, 20):
		c.add(a ** i)
		d.add(b ** i)
	s = c.intersection(d)
	if s:
		print('YES')
	else:
		print('NO')


from math import gcd

def s(a, b):
	(b, a) = (a, b)

def solve():
	(A, B) = map(int, input().split())
	if A == B:
		print('YES')
	else:
		while gcd(A, B) != 1 and A != B:
			if A > B:
				A = A // gcd(A, B)
			else:
				B = B // gcd(A, B)
		if A == 1 or B == 1 or A == B:
			print('YES')
		else:
			print('NO')
T = int(input())
while T > 0:
	solve()
	T -= 1


from math import gcd
a = int(input())
for i in range(a):
	(A, B) = map(int, input().split())
	while gcd(A, B) != 1:
		if A > B:
			A = A // gcd(A, B)
		else:
			B = B // gcd(A, B)
	if A == 1 or B == 1:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(a, b) = [int(i) for i in input().split()]
	a1 = set()
	b1 = set()
	for i in range(1, 25):
		a1.add(a ** i)
		b1.add(b ** i)
	s = a1.intersection(b1)
	if s:
		print('YES')
	else:
		print('NO')


import math

def solve(List):
	lna = math.log(List[0])
	lnb = math.log(List[1])
	for y in range(1, 501):
		if (y * lnb / lna).is_integer():
			return True
	return False
Input = [[int(i) for i in input().split(' ')] for i in range(0, int(input()))]
for List in Input:
	if solve(List) == True:
		print('YES')
	else:
		print('NO')


from fractions import Fraction
import math
primes = [1 for i in range(int(1000000.0 + 1))]
prime = []

def sieve():
	primes[0] = 0
	primes[1] = 0
	i = 2
	while i * i <= int(1000000.0):
		if primes[i]:
			prime.append(i)
			j = i * i
			while j <= int(1000000.0):
				primes[j] = 0
				j += i
		i += 1
	i = int(1000.0 + 1)
	while i <= int(1000000.0):
		if primes[i]:
			prime.append(i)
		i += 1

def factors(n):
	fac = []
	i = 0
	while i < len(prime) and prime[i] * prime[i] <= n:
		cnt = 0
		x = prime[i]
		while n % x == 0:
			cnt += 1
			n = int(n / x)
		if cnt > 0:
			fac.append([x, cnt])
		i += 1
	if n > 1:
		fac.append([n, 1])
	return fac
sieve()
T = int(input())
for _ in range(T):
	(A, B) = [int(i) for i in input().split(' ')]
	if A == B:
		print('YES')
		continue
	aFactors = factors(A)
	bFactors = factors(B)
	rat = set()
	(n, m) = (len(aFactors), len(bFactors))
	if n != m:
		print('NO')
		continue
	flag = True
	for i in range(n):
		if aFactors[i][0] != bFactors[i][0]:
			flag = False
			break
		x = aFactors[i][1]
		y = bFactors[i][1]
		gcd = math.gcd(x, y)
		x = x // gcd
		y = y // gcd
		rat.add(f'{x}-{y}')
	if flag and len(rat) == 1:
		print('YES')
	else:
		print('NO')


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

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
from math import gcd
for _ in range(int(input())):
	(a, b) = mi()
	while gcd(a, b) != 1:
		if a > b:
			a = a // gcd(a, b)
		else:
			b = b // gcd(a, b)
	print('YES' if a == 1 or b == 1 else 'NO')


def primefactorization(n):
	l = [-1] * (n + 1)
	for i in range(2, n):
		if l[i] == -1:
			for j in range(i, n + 1, i):
				l[j] = i
	return l
l = primefactorization(10 ** 6 + 1)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l1 = []
	l2 = []
	s1 = set()
	s2 = set()
	while a > 0:
		if l[a] != -1:
			l1.append(l[a])
			s1.add(l[a])
		a = int(a / l[a])
	while b > 0:
		if l[b] != -1:
			l2.append(l[b])
			s2.add(l[b])
		b = int(b / l[b])
	ans = set()
	if s1 == s2:
		for i in s1:
			ans.add(l1.count(i) / l2.count(i))
			if len(ans) > 1:
				print('NO')
				break
		else:
			print('YES')
	else:
		print('NO')


cache = [i for i in range(1000001)]
for i in range(2, 1000001):
	for j in range(i * i, 1000001, i):
		if cache[j] == j:
			cache[j] = i

def compute_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def compute_lcm(x, y):
	lcm = x * y // compute_gcd(x, y)
	return lcm
mod = 1000000007

def check(a, b):
	if cache[a] != cache[b]:
		return 'NO'
	p = q = 0
	spa = cache[a]
	spb = cache[b]
	while a % spa == 0:
		a = a // spa
		p += 1
	while b % spb == 0:
		b = b // spb
		q += 1
	lcm = compute_lcm(p, q)
	x = lcm // p
	y = lcm // q
	a1 = pow(a, x) % mod
	b1 = pow(b, y) % mod
	return 'YES' if a1 == b1 else 'NO'
t = int(input())
while t != 0:
	(a, b) = map(int, input().split(' '))
	print(check(a, b))
	t -= 1


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


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


import math

def fact(n):
	l = []
	while n % 2 == 0:
		l += [2]
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l += [i]
			n = n // i
	if n > 2:
		l += [n]
	return l
t = int(input(''))
for i in range(0, t):
	x = input('')
	x = x.split(' ')
	num1 = int(x[0])
	num2 = int(x[1])
	l1 = fact(num1)
	fakel1 = []
	l2 = fact(num2)
	dic1 = {}
	dic2 = {}
	for ele in l1:
		if ele in fakel1:
			dic1[ele] = int(dic1[ele]) + 1
		else:
			dic1[ele] = 1
		fakel1 += [ele]
	fakel1 = []
	for ele in l2:
		if ele in fakel1:
			dic2[ele] = int(dic2[ele]) + 1
		else:
			dic2[ele] = 1
		fakel1 += [ele]
	if len(dic1) != len(dic2):
		print('NO')
	else:
		newl1 = dic1.keys()
		newl2 = dic2.keys()
		newl3 = []
		newl4 = []
		for ele in newl1:
			newl3 += [ele]
		for ele in newl2:
			newl4 += [ele]
		if newl3 == newl4 and len(newl3) == 1:
			print('YES')
		elif newl3 == newl4 and len(newl4) != 1:
			count = 0
			i = 0
			x = int(dic1[newl4[0]])
			y = int(dic2[newl4[0]])
			z = x / y
			for ele in newl1:
				if i > 0:
					x = dic1[ele]
					y = dic2[ele]
					m = x / y
					if z != m:
						count = 1
						break
				i += 1
			if count == 0:
				print('YES')
			else:
				print('NO')
		else:
			print('NO')


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(acob, bcob) = (a, b)
	c = 30
	x = 0
	while c > 0:
		c -= 1
		if a == b:
			x = 1
			break
		if a < b:
			a *= acob
		if b < a:
			b *= bcob
	print('YES' if x == 1 else 'NO')


from collections import defaultdict as dd
from fractions import Fraction as F
primes = []
for n in range(2, 1010):
	if all((n % p != 0 for p in primes)):
		primes.append(n)

def find_primes(n):
	factors = dd(int)
	for p in primes:
		while n % p == 0:
			factors[p] += 1
			n //= p
		if n == 1:
			break
	if n != 1:
		factors[n] += 1
	return factors
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	p1 = find_primes(a)
	p2 = find_primes(b)
	if sorted(p1.keys()) != sorted(p2.keys()):
		print('NO')
		continue
	frac = None
	for (k, v1) in p1.items():
		v2 = p2[k]
		if frac is None:
			frac = F(v1, v2)
		if frac != F(v1, v2):
			break
	else:
		print('YES')
		continue
	print('NO')


n = 1000001
(*a,) = range(n)
i = 2
while i * i < n:
	j = i
	while j < n:
		if a[j] > i:
			a[j] = i
		j *= i
	i += 1
for i in range(int(input())):
	(x, y) = map(int, input().split())
	if a[x] == a[y]:
		print('YES')
	else:
		print('NO')


import math

def primeFactors(n):
	l = []
	c = 0
	while n % 2 == 0:
		n = n // 2
		c += 1
	if c != 0:
		l.append([2, c])
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		c = 0
		while n % i == 0:
			n = n // i
			c += 1
		if c != 0:
			l.append([i, c])
	if n > 2:
		l.append([n, 1])
	return l
t = int(input())
for x in range(t):
	A = [int(b) for b in input().split()]
	a = A[0]
	b = A[1]
	l1 = primeFactors(a)
	l2 = primeFactors(b)
	ln1 = len(l1)
	ln2 = len(l2)
	flag = 0
	if ln1 == 1 and ln2 == 1 and (l1[0][0] == l2[0][0]):
		print('YES')
	elif ln1 == ln2 and ln1 != 1:
		for j in range(ln1):
			if l1[j][0] == l2[j][0] and j == 0:
				tm1 = [l1[j][1], l2[j][1]]
			elif l1[j][0] == l2[j][0]:
				tm2 = [l1[j][1], l2[j][1]]
				if tm2[0] * tm1[1] != tm2[1] * tm1[0]:
					flag = 1
					break
			else:
				flag = 1
				break
		if flag == 1:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


import math
t = int(input())
for x in range(t):
	A = [int(b) for b in input().split()]
	a = A[0]
	b = A[1]
	flag = False
	for i in range(1, 20):
		x1 = math.log(a) * i / math.log(b)
		if math.isclose(round(x1), x1):
			flag = True
			break
	if flag:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split(' '))
	l1 = []
	l2 = []
	for i in range(1, 20):
		l1.append(pow(a, i))
	for i in range(1, 20):
		l2.append(pow(b, i))
	l3 = [i for i in l1 if i in l2]
	if len(l3) > 0:
		print('YES')
	else:
		print('NO')


from collections import defaultdict
import math as mt

def factors(n):
	i = 2
	x = []
	while i * i <= n:
		if n % i == 0:
			cnt = 0
			while n % i == 0:
				n //= i
				cnt += 1
			x.append([i, cnt])
		i += 1
	if n != 1:
		x.append([n, 1])
	return x
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	pfa = factors(a)
	pfb = factors(b)
	flag = True
	if len(pfa) == len(pfb):
		curr = [0, 0]
		for i in range(len(pfa)):
			(x, y) = pfa[i]
			(p, q) = pfb[i]
			if x != p:
				flag = False
				break
			if i == 0:
				g = mt.gcd(y, q)
				y //= g
				q //= g
				curr[0] = y
				curr[1] = q
			else:
				g = mt.gcd(y, q)
				chk = [y // g, q // g]
				if chk != curr:
					flag = False
					break
		if flag:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


import math as mt
MAXN = 1000001
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = dict()
	while x != 1:
		if spf[x] not in ret:
			ret[spf[x]] = 0
		ret[spf[x]] += 1
		x = x // spf[x]
	return ret
sieve()

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

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
for t in range(int(input())):
	(a, b) = mi()
	if a > b:
		(a, b) = (b, a)
	x = getFactorization(a)
	y = getFactorization(b)
	if not set(x.keys()) == set(y.keys()):
		print('NO')
		continue
	flag = True
	val = set()
	for i in x:
		if x[i] > y[i]:
			flag = False
		val.add(y[i] / x[i])
	if len(val) == 1 and flag:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(a, b) = map(int, input().split())
	while True:
		(a, b) = (max(a, b), min(a, b))
		if a % b == 0:
			a /= b
			if a == 1:
				print('YES')
				break
			elif a == 0:
				break
		else:
			print('NO')
			break


import math
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ap = []
	bp = []
	sqrta = math.sqrt(a)
	sqrtb = math.sqrt(b)
	i = 0
	while prime[i] <= sqrta:
		if a % prime[i] == 0:
			ap.append(prime[i])
			a = a // prime[i]
		else:
			i += 1
	if a != 1:
		ap.append(a)
	j = 0
	while prime[j] <= sqrtb:
		if b % prime[j] == 0:
			bp.append(prime[j])
			b = b // prime[j]
		else:
			j += 1
	if b != 1:
		bp.append(b)
	aps = set(ap)
	bps = set(bp)
	if aps != bps:
		print('NO')
	else:
		ratio = len(bp) / len(ap)
		is_eq = True
		for item in aps:
			if bp.count(item) / ap.count(item) != ratio:
				is_eq = False
				break
		if is_eq:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	(x, y) = [int(x) for x in input().split()]
	val = 30
	k = []
	while val >= 1:
		k.append(x ** val)
		k.append(y ** val)
		val -= 1
	a = len(k)
	b = len(set(k))
	if a != b:
		print('YES')
	else:
		print('NO')


import random
t = int(input())
for i in range(t):
	(A, B) = map(int, input().split())
	while True:
		(A, B) = (max(A, B), min(A, B))
		if A % B == 0:
			X = A // B
			A = B
			B = X
			if B == 1:
				print('YES')
				break
			elif X == 0:
				break
		else:
			print('NO')
			break


def solve():
	(a, b) = map(int, input().split())
	while 1:
		(a, b) = (max(a, b), min(a, b))
		if a % b == 0:
			x = a / b
			a = b
			b = x
			if b == 1:
				print('YES')
				break
			elif x == 0:
				break
		else:
			print('NO')
			break
for _ in range(int(input())):
	solve()


def main():
	for _ in range(int(input())):
		(a, b) = map(int, input().split())
		(a, b) = (max(a, b), min(a, b))
		f = 0
		while a % b == 0:
			c = a / b
			if c == 1:
				f = 1
				break
			a = max(b, c)
			b = min(b, c)
		print('YES' if f else 'NO')
main()


def check(a, b):
	x = 1
	y = 1
	while x <= 30 and y <= 30:
		Ax = pow(a, x)
		By = pow(b, y)
		if Ax == By:
			return True
		elif Ax < By:
			x += 1
		else:
			y += 1
	return False
K = int(input())
for i in range(K):
	(r, p) = map(int, input().split())
	if check(r, p):
		print('YES')
	else:
		print('NO')


def check(a, b):
	k = 0
	while k == 0:
		k = max(a, b) % min(a, b)
		q = max(a, b) / min(a, b)
		(a, b) = (q, min(a, b))
		if q == 1:
			break
	if q == 1:
		return 'YES'
	else:
		return 'NO'
K = int(input())
for i in range(K):
	(r, p) = map(int, input().split())
	print(check(r, p))


def solve():
	k = 0
	(a, b) = map(int, input().split())
	while k == 0:
		k = max(a, b) % min(a, b)
		q = max(a, b) / min(a, b)
		(a, b) = (q, min(a, b))
		if q == 1:
			break
	if q == 1:
		print('YES')
	else:
		print('NO')
t = int(input())
for i in range(t):
	solve()


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	al = []
	bl = []
	for i in range(1, 20):
		al.append(a ** i)
		bl.append(b ** i)
	a = set(al)
	b = set(bl)
	if a.intersection(b):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	(smaller, greater) = (min(a, b), max(a, b))
	while True:
		if greater % smaller != 0:
			print('NO')
			break
		greater = greater / smaller
		if greater < smaller:
			(greater, smaller) = (smaller, greater)
		if smaller == 1:
			print('YES')
			break


for i in range(int(input())):
	(A, B) = map(int, input().split())
	(smaller, greater) = (min(A, B), max(A, B))
	while True:
		if greater % smaller != 0:
			print('NO')
			break
		greater = greater / smaller
		if greater < smaller:
			(greater, smaller) = (smaller, greater)
		if smaller == 1:
			print('YES')
			break


import math
for testcase in range(int(input())):
	(a, b) = map(int, input().split())
	aa = -1
	p = 2
	while p * p <= a:
		if a % p == 0:
			aa = p
			break
		p += 1
	if aa == -1:
		aa = a
	da = 0
	db = 0
	while a % aa == 0:
		da += 1
		a //= aa
	while b % aa == 0:
		db += 1
		b //= aa
	if pow(a, db) == pow(b, da):
		print('YES')
	else:
		print('NO')