You are given two positive integers a and b. You also have a number x, which is initially set to 0. At first, you can add a to x any number of times. After that, you can divide x by b any number of times as long as x is divisible by b.

Print YES if you can make x equal to 1, otherwise print NO.

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

- First line of input will contain T, the number of test cases. Then the test cases follow.
- Each test case contains a single line, two positive integers a, b.

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

For each test case, output on one line YES if it is possible to make x , or NO if it is not possible to do so. 

Output is case insensitive, which means that "yes", "Yes", "YEs", "no", "nO" - all such strings will be acceptable.

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

$1 ≤ T ≤ 100000$
$1 ≤ a, b ≤ 10^{9}$

----- Sample Input 1 ------ 
4
3 10
9 6
7 30
8 12
----- Sample Output 1 ------ 
NO
YES
NO
YES
----- explanation 1 ------ 
Test case $2$: We initially have $x$ set to $0$. Add $a = 9$ to $x$ for $4$ times to make $x$ equal to $36$. And then divide $x$ by $b = 6$ for $2$ times to make $x$ equal to $1$.

Test case $4$: We initially have $x$ set to $0$. Add $a = 8$ to $x$ for $18$ times to make $x$ equal to $144$. And then divide $x$ by $b = 12$ for $2$ times to make $x$ equal to $1$.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(a, b) = tuple(map(int, input().split()))
	p = False
	r = b
	for i in range(100):
		if r % a == 0:
			p = True
			break
		else:
			r *= b
	if p:
		print('YES')
	else:
		print('NO')


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


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


T = int(input())
for __ in range(T):
	(a, b) = list(map(int, input().split()))
	isPossible = False
	q = b
	for i in range(50):
		if q % a == 0:
			isPossible = True
			break
		else:
			q *= b
	if isPossible:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(a, b) = map(int, input().split())
	x = 0
	if b == 1:
		print('NO')
	elif a == b:
		print('YES')
	elif a == 1:
		print('YES')
	else:
		while b <= 10 ** 500:
			if b % a == 0:
				x = 1
				print('YES')
				break
			else:
				b = b * b
		if x == 0:
			print('NO')


import math
test = int(input())
for kk in range(test):
	(x, y) = map(int, input().split())
	while True:
		a = math.gcd(x, y)
		if a == 1:
			break
		x = int(x / a)
	if x == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	f = False
	for j in range(1, 31):
		if b ** j % a == 0:
			f = True
			break
	print('YES' if f else 'NO')


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	found = False
	for i in range(1, 31):
		if b ** i % a == 0:
			found = True
			break
	if found:
		print('YES')
	else:
		print('NO')


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


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


t = int(input())
for zz in range(t):
	(a, b) = map(int, input().split())
	c = 0
	v = b
	for i in range(100):
		if v % a == 0:
			c = 1
			break
		else:
			v *= b
	if c == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	temp = b
	pos = True
	for i in range(50):
		if temp % a == 0:
			pos = False
			break
		temp = temp * b
	if pos:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	if b % a == 0:
		print('YES')
	elif b == 1:
		print('NO')
	else:
		ans = 'NO'
		for i in range(2, 30):
			if b ** i % a == 0:
				ans = 'YES'
				break
		print(ans)


from collections import *
for u in range(int(input())):
	(a, b) = map(int, input().split())
	s = b
	f = 0
	for i in range(100):
		if s % a == 0:
			f = 1
			break
		else:
			s *= b
	if f == 0:
		print('NO')
	else:
		print('YES')


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


import heapq as hp
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	f = 0
	for i in range(32):
		if b % a == 0:
			f = 1
			break
		else:
			b *= b
			b %= a
	if f:
		print('YES')
	else:
		print('NO')


for j in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	d = 0
	for i in range(1, 30):
		if k ** i % n == 0:
			print('YES')
			d += 1
			break
	if d == 0:
		print('NO')


t = int(input())
while t > 0:
	t = t - 1
	(a, b) = map(int, input().split())
	r = b
	c = False
	for i in range(0, 100):
		if r % a == 0:
			c = True
			break
		else:
			r = r * b
	if c == True:
		print('YES')
	else:
		print('NO')


import math
import sys
MOD = 1000000007

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

def ii():
	return int(inp())

def iis():
	return [int(i) for i in inp().split()]

def solve():
	(a, b) = iis()
	while a != 1:
		if math.gcd(a, b) == 1:
			return False
		a //= math.gcd(a, b)
	return True
t = ii()
for _ in range(t):
	print('YES' if solve() else 'NO')


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


def hcf(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = int(input())
while t:
	t -= 1
	(x, y) = map(int, input().split())
	h = hcf(x, y)
	while h > 1:
		h = hcf(x, y)
		x /= h
		if h == 1:
			break
	if x != 1:
		print('NO')
	else:
		print('YES')


from math import gcd
test = int(input())
for t in range(test):
	(a, b) = map(int, input().split())
	if b % a == 0:
		print('YES')
	else:
		x = b
		ok = False
		while gcd(a, x) != 1:
			m = gcd(a, x)
			x //= m
			a //= m
			if a == 1:
				ok = True
				break
			x *= b
		if not ok:
			print('NO')
		else:
			print('YES')


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


t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	n = y
	f = 0
	for i in range(50):
		if n % x == 0:
			f = 1
			break
		n = n * y
	if f:
		print('YES')
	else:
		print('NO')


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


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = math.gcd(a, b)
	x = a // c
	if pow(b, x, a) == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	po = b
	check = False
	for _ in range(100):
		if po % a == 0:
			check = True
			break
		po = po * b
	if check == True:
		print('YES')
	else:
		print('NO')


import sys
import math
import heapq
from collections import defaultdict as dd
from collections import OrderedDict as od
from collections import deque
from itertools import permutations as pp
from itertools import combinations as cc
from sys import stdin
from functools import cmp_to_key as ctk
from functools import lru_cache
from bisect import bisect_left as bs_l
from bisect import bisect_right as bs_r
input = sys.stdin.readline
mod = 10 ** 9 + 7
sys.setrecursionlimit(2 * 10 ** 5 + 1)

def comparator(x, y):
	if x[0] == y[0]:
		return x[1] - y[1]
	return True

def ncr(n, r):
	if n < r:
		return 0
	return fc[n] * pow(fc[r] * fc[n - r] % mod, mod - 2, mod) % mod
T = int(input())
for _ in range(T):
	(a, b) = map(int, input().split())
	if b == 1:
		if a == 1:
			print('YES')
		else:
			print('NO')
	else:
		f = 0
		pp = 1
		for i in range(31):
			if b ** pp % a == 0:
				f = 1
				break
			pp += 1
		if f:
			print('YES')
			continue
		print('NO')


t = int(input())
while t:
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	power = 1
	poss = False
	for i in range(1, 100):
		power *= b
		if power % a == 0:
			poss = True
			break
	if poss:
		print('YES')
	else:
		print('NO')
	t -= 1


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 True:
		x = gcd(a, b)
		if x == 1:
			break
		a //= x
	if a == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	k = 0
	for i in range(30):
		if pow(b, i) % a == 0:
			print('YES')
			k += 1
			break
	if k == 0:
		print('NO')


def check(a, b):
	for i in range(1, 31):
		if b ** i % a == 0:
			return 'YES'
	return 'NO'
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	print(check(a, b))


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


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


n = int(input())
for _ in range(n):
	(a, b) = map(int, input().split())
	flag = False
	for i in range(1, 30):
		if b ** i % a == 0:
			flag = True
			break
	if flag:
		print('YES')
	else:
		print('NO')


def inIntList():
	return [int(x) for x in input().split()]

def inInt():
	return int(input())

def outList(lst):
	for data in lst:
		print(data)

def solveA():
	for _ in range(inInt()):
		(M, N, K) = inIntList()
		ans.append('YES' if M > N * K else 'NO')

def solveB():
	for _ in range(inInt()):
		(N, P, X, Y) = inIntList()
		A = inIntList()
		child = A[:P].count(0)
		elder = P - child
		ans.append(X * child + Y * elder)

def solveC():
	for _ in range(inInt()):
		S = input()
		old = S[0]
		wand = 1 if old == '0' else 0
		for new in S[1:]:
			if old != new:
				wand += 1
				old = new
		ans.append(wand)

def solveD():
	for _ in range(inInt()):
		(P, a, b, c, x, y) = inIntList()
		ans.append(P // min(b + a * x, c + a * y))

def solveE():
	for _ in range(inInt()):
		(a, b) = inIntList()
		for i in range(1, 30):
			if b ** i % a == 0:
				ans.append('YES')
				break
		else:
			ans.append('NO')
ans = []
solveE()
outList(ans)


import math

def lcm(a, b):
	return a * b / math.gcd(a, b)
for r in range(int(input())):
	(a, b) = list(map(int, input().split()))
	gcd1 = math.gcd(a, b)
	if a == b == 1:
		print('YES')
		continue
	while a > 1 and gcd1 > 1:
		a = a // gcd1
		gcd1 = math.gcd(a, b)
	if a == 1 and gcd1 == 1:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	num = 1
	cnt = 0
	flag = 0
	while cnt <= 100:
		if num % a == 0:
			print('YES')
			flag = 1
			break
		num *= b
		cnt += 1
	if flag == 0:
		print('NO')


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


from math import gcd
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	while gcd(a, b) != 1:
		a = a // gcd(a, b)
	if a == 1:
		sys.stdout.write('YES\n')
	else:
		sys.stdout.write('NO\n')


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


for i in range(int(input())):
	(x, y) = map(int, input().split())
	print(['YES', 'NO'][pow(y, 100, x) != 0])


def solve():
	(a, b) = map(int, input().split())
	r = b
	p = 0
	for i in range(100):
		if r % a == 0:
			p = 1
			break
		else:
			r = r * b
	if p == 1:
		print('YES')
	else:
		print('NO')
t = int(input())
while t:
	solve()
	t -= 1


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	flag = False
	i = 0
	x = b
	while i < 100:
		x = x * b
		if x % a == 0:
			flag = True
			break
		i += 1
	if flag:
		print('YES')
	else:
		print('NO')


import math
import sys
import collections
import bisect
import time
import random
import itertools
import string
from collections import Counter, defaultdict

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

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

def get_string():
	return sys.stdin.readline().strip()
for t in range(int(input())):
	(a, b) = get_ints()
	poss = True
	g = math.gcd(a, b)
	while g != 1:
		a //= g
		g = math.gcd(a, b)
	if a == 1:
		print('YES')
	else:
		print('NO')


from math import gcd

def solve(a, b):
	while True:
		g = gcd(a, b)
		if g != 1:
			a //= g
			continue
		if a == 1:
			return 'YES'
		return 'NO'
	return 'NO'
t = int(input().strip())
inputs = []
for _ in range(t):
	(a, b) = map(int, input().strip().split())
	inputs.append((a, b))
for (a, b) in inputs:
	print(solve(a, b))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	f = True
	for i in range(1, 30):
		p = b ** i
		if p % a == 0:
			print('YES')
			f = False
			break
	if f:
		print('NO')


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


def main():
	for _ in range(int(input())):
		(a, b) = map(int, input().split())
		flg = 0
		for i in range(1, 50):
			if b ** i % a == 0:
				flg = 1
				break
		print('YES' if flg else 'NO')
main()


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	m = pow(b, 100) % a
	if b % a == 0 or m == 0:
		print('YES')
	else:
		print('NO')


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


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


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


try:
	TC = int(input())
	for i in range(TC):
		(a, b) = map(int, input().split())
		x = 1
		count = False
		for i in range(1, 100):
			x *= b
			if x % a == 0:
				count = True
				break
		if count:
			print('YES')
		else:
			print('NO')
except:
	pass