There is an infinite set generated as follows:

$1$ is in this set.

If $x$ is in this set, $x \cdot a$ and $x+b$ both are in this set.

For example, when $a=3$ and $b=6$, the five smallest elements of the set are:

$1$,

$3$ ($1$ is in this set, so $1\cdot a=3$ is in this set),

$7$ ($1$ is in this set, so $1+b=7$ is in this set),

$9$ ($3$ is in this set, so $3\cdot a=9$ is in this set),

$13$ ($7$ is in this set, so $7+b=13$ is in this set).

Given positive integers $a$, $b$, $n$, determine if $n$ is in this set.


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1\leq t\leq 10^5$) — the number of test cases. The description of the test cases follows.

The only line describing each test case contains three integers $n$, $a$, $b$ ($1\leq n,a,b\leq 10^9$) separated by a single space.


-----Output-----

For each test case, print "Yes" if $n$ is in this set, and "No" otherwise. You can print each letter in any case.


-----Examples-----

Input
5
24 3 5
10 3 6
2345 1 4
19260817 394 485
19260817 233 264
Output
Yes
No
Yes
No
Yes


-----Note-----

In the first test case, $24$ is generated as follows:

$1$ is in this set, so $3$ and $6$ are in this set;

$3$ is in this set, so $9$ and $8$ are in this set;

$8$ is in this set, so $24$ and $13$ are in this set.

Thus we can see $24$ is in this set.

The five smallest elements of the set in the second test case is described in statements. We can see that $10$ isn't among them.

Source: codeforces | Difficulty: MEDIUM
Tags: Number theory

Mathematics

Constructive algorithms


Solutions:
def solv(n, a, b):
	curr_val = 1
	while True:
		if curr_val > n:
			return 'No'
		if (n - curr_val) % b == 0:
			return 'Yes'
		if a == 1:
			return 'No'
		curr_val = curr_val * a
t = int(input())
for i in range(0, t):
	(n, a, b) = input().split()
	print(solv(int(n), int(a), int(b)))


t = int(input())
while t > 0:
	x = input()
	y = x.split()
	n = int(y[0])
	a = int(y[1])
	b = int(y[2])
	flag = False
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		k = 1
		while k <= n:
			if k % b == n % b:
				flag = True
				break
			k = k * a
		if flag:
			print('Yes')
		else:
			print('No')
	t -= 1


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		t = 1
		while t <= n:
			if (n - t) % b == 0:
				print('Yes')
				break
			t = t * a
		else:
			print('No')


for _ in range(int(input())):
	(n, a, b) = list(map(int, input().split()))
	if n == 1 or b == 1:
		print('Yes')
	elif a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		ans = 'No'
		x = 1
		while x <= n:
			if (n - x) % b == 0:
				ans = 'Yes'
				break
			else:
				x *= a
		print(ans)


def solve():
	(n, a, b) = [int(s) for s in input().split(' ')]
	if a == 1:
		if n % b == 1 or b == 1:
			print('Yes')
		else:
			print('No')
		return
	p = 1
	while p <= n:
		if b == 1 or n % b == p % b:
			print('Yes')
			return
		p *= a
	print('No')
t = int(input())
for _ in range(t):
	solve()


from math import log, ceil

def main():
	t = int(input())
	for _ in range(t):
		(n, a, b) = [int(x) for x in input().split()]
		if b == 1:
			print('Yes')
		elif a == 1:
			if (n - 1) % b == 0:
				print('Yes')
			else:
				print('No')
		else:
			max_power = ceil(log(n, a))
			curr_power = 1
			flag_failed = True
			for i in range(max_power + 1):
				if curr_power > n:
					break
				if (n - curr_power) % b == 0:
					print('Yes')
					flag_failed = False
					break
				curr_power *= a
			if flag_failed:
				print('No')
main()


t = int(input())
for i in range(t):
	w = input().split()
	n = int(w[0])
	a = int(w[1])
	b = int(w[2])
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		t = 1
		flag = 0
		while t <= n:
			if t % b == n % b:
				flag = 1
				break
			t = t * a
		if flag == 1:
			print('Yes')
		else:
			print('No')


test_cases = int(input())
for test_case in range(test_cases):
	(n, a, b) = list(map(int, input().split()))
	ans = 'No'
	if (n - 1) % b == 0:
		ans = 'Yes'
	if n == a:
		ans = 'Yes'
	x = a
	while a != 1:
		if (n - x) % b == 0:
			ans = 'Yes'
			break
		else:
			x *= a
		if n - x < 0:
			break
	print(ans)


t = int(input())
for i in range(t):
	(n, a, b) = map(int, input().split())
	if b == 1:
		print('Yes')
		continue
	if a == 1:
		print('Yes' if n % b == 1 else 'No')
	else:
		p = 1
		r = n % b
		valid = False
		while p <= n:
			if r == p % b:
				valid = True
				break
			p = p * a
		if valid:
			print('Yes')
		else:
			print('No')


for t in range(int(input())):
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('YES')
		else:
			print('NO')
	else:
		x = 1
		d = True
		while x <= n:
			if (n - x) % b == 0:
				d = False
				break
			x *= a
		if not d:
			print('YES')
		else:
			print('NO')


k = int(input())
while k > 0:
	Z = [int(i) for i in input().split(' ')]
	n = Z[0]
	a = Z[1]
	b = Z[2]
	if a == 1:
		if (n - 1) % b == 0:
			print('YES')
		else:
			print('NO')
	else:
		c = 1
		C = []
		while c <= n:
			if c % b == n % b:
				C = C + [c]
				print('YES')
				break
			c = c * a
		if len(C) == 0:
			print('No')
	k = k - 1


import sys

def solve(N, A, B):
	if B == 1:
		return 'Yes'
	if A == 1:
		if N % B == 1:
			return 'Yes'
		else:
			return 'No'
	val = 1
	while val <= N:
		if (N - val) % B == 0:
			return 'Yes'
		val *= A
	return 'No'

def run():
	out = ''
	T = int(input())
	res_list = []
	for i in range(T):
		(N, A, B) = [int(x) for x in sys.stdin.readline().split()]
		res_list.append(solve(N, A, B))
	print('\n'.join(res_list))
run()


t = int(input())
for i in range(0, t):
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		q = 1
		flag = 0
		while q <= n:
			if (n - q) % b == 0:
				print('Yes')
				flag = 1
				break
			q = q * a
		if flag == 0:
			print('No')


from sys import *
import math
input = stdin.readline
I = int
R = range
listInput = lambda : list(map(int, input().strip().split()))
lineInput = lambda : map(int, input().strip().split())
sJoin = lambda a, sep: '{}'.format(sep).join(a)
arrJoin = lambda a, sep: '{}'.format(sep).join(map(str, a))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	for i in range(5, int(math.sqrt(n) + 1), 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

def main():
	for k in R(I(input())):
		(n, a, b) = lineInput()
		if a == 1:
			print('YES') if (n - 1) % b == 0 else print('NO')
		else:
			s = 1
			flag = False
			while s <= n:
				if (n - s) % b == 0:
					flag = True
					break
				s *= a
			print('YES') if flag else print('NO')
main()


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


from math import *
for t in range(int(input())):
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
			continue
		else:
			print('No')
			continue
	found = 'No'
	for p in range(0, int(log(n, a) + 2)):
		x = n - a ** p
		if x >= 0:
			if x % b == 0:
				found = 'Yes'
				break
	print(found)


import sys

class FastIO:

	def next(self):
		return sys.stdin.readline().split('\n')[0]

	def nextint(self):
		return int(sys.stdin.readline().split('\n')[0])

	def print(self, d):
		sys.stdout.write(str(d))

	def println(self, d):
		sys.stdout.write(str(d) + '\n')

	def printls(self, d, p):
		for i in d:
			sys.stdout.write(str(i) + p)
sc = FastIO()
for _ in range(sc.nextint()):
	(n, a, b) = map(int, sc.next().split())
	ans = 'No'
	i = 1
	if a == 1:
		if (n - 1) % b == 0:
			ans = 'Yes'
	else:
		while n >= i:
			if (n - i) % b == 0:
				ans = 'Yes'
				break
			i = i * a
	sc.println(ans)


import sys

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def void():
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		i = 1
		valid = False
		while i <= n:
			if (n - i) % b == 0:
				valid = True
				break
			i *= a
		if valid:
			print('Yes')
		else:
			print('No')
for i in range(int(input())):
	void()


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	f = False
	if a == 1:
		if (n - 1) % b == 0:
			f = True
	else:
		k = 1
		while k <= n:
			if k % b == n % b:
				f = True
				break
			k *= a
	if f:
		print('Yes')
	else:
		print('No')


import sys
import io, os
import math
gcd = math.gcd
sqrt = math.sqrt
ceil = math.ceil

def strinp(testcases):
	k = 5
	if testcases == -1 or testcases == 1:
		k = 1
	f = str(input())
	f = f[2:len(f) - k]
	return f

def checker(x, y, a, b):
	if (x - 1) % a != 0:
		return False
	trig = True
	while y != 1:
		if y % b != 0:
			trig = False
			break
		y = y // b

def factors(n):
	p = int(sqrt(n))
	ans = []
	for i in range(1, p + 1):
		if n % i == 0:
			if n // i == i:
				ans.append([i, i])
			else:
				ans.append([i, n // i])
	ans.sort()
	return ans

def print(x, end='\n'):
	sys.stdout.write(str(x) + end)

def main():
	t = int(input())
	for _ in range(t):
		arr = list(map(int, input().split()))
		n = arr[0]
		a = arr[1]
		b = arr[2]
		if a == 1:
			if (n - 1) % b == 0:
				print('Yes')
			else:
				print('No')
			continue
		f = 1
		trig = False
		while n - f > -1:
			if (n - f) % b == 0:
				trig = True
				break
			f *= a
		if trig:
			print('Yes')
		else:
			print('No')
main()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(3 * 10 ** 5)

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	(n, a, b) = ma()
	if a == 1:
		if (n - 1) % b:
			print('No')
		else:
			print('Yes')
	else:
		x = 1
		s = 'No'
		while x <= n:
			if x % b == n % b:
				s = 'Yes'
				break
			x *= a
		print(s)


import sys, io, os, math, bisect, heapq
from collections import Counter, deque, defaultdict
try:
	inp = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
	inp = lambda : sys.stdin.readline().encode()
L = lambda : list(map(int, inp().split()))
I = lambda : int(inp())
S = lambda : inp().strip().decode()
C = lambda : inp().split()

def pr(a):
	print(' '.join(list(map(str, a))))

def solve():
	(n, a, b) = L()
	x = 1
	while n >= x:
		if (n - x) % b == 0:
			print('YES')
			return
		if a == 1:
			break
		x *= a
	print('NO')
for _ in range(I()):
	solve()


from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	(n, a, b) = list(map(int, stdin.readline().split()))
	f = 0
	c = 1
	if a == 1:
		if (n - 1) % b == 0:
			stdout.write('yes\n')
		else:
			stdout.write('no\n')
	else:
		while c <= n:
			if (n - c) % b == 0:
				stdout.write('yes\n')
				f = 1
				break
			c = c * a
		if f == 0:
			stdout.write('no\n')


import sys
input = sys.stdin.readline

def main():
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
		return
	x = 1
	while x <= n:
		if (n - x) % b == 0:
			print('Yes')
			return
		x *= a
	print('No')
for _ in range(int(input())):
	main()


for _ in range(int(input())):
	(n, a, b) = list(map(int, input().split()))
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		m = 1
		flag = False
		while m <= n:
			if m % b == n % b:
				flag = True
				break
			m *= a
		if flag:
			print('Yes')
		else:
			print('No')


t = int(input())
while t != 0:
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		i = 1
		while i <= n:
			if (n - i) % b == 0:
				print('Yes')
				break
			i *= a
		if i > n:
			print('No')
	t -= 1


t = int(input())
while t != 0:
	(n, a, b) = map(int, input().split())
	c = 1
	mk = 0
	while c <= n:
		if (n - c) % b == 0:
			print('YES')
			mk = 1
			break
		if a == 1:
			break
		else:
			c = c * a
	if mk != 1:
		print('NO')
	t = t - 1


def check(n, a, b):
	end = n
	if a == 1:
		if (n - 1) % b == 0:
			return 'Yes'
		else:
			return 'No'
	z = 1
	while z <= n:
		if (n - z) % b == 0:
			return 'Yes'
			break
		z = z * a
	return 'No'
t = int(input())
for i in range(t):
	(n, a, b) = map(int, input().split())
	print(check(n, a, b))


t = int(input())
for ll in range(t):
	(n, a, b) = map(int, input().split(' '))
	if a == 1:
		if n % b == 1 % b:
			print('Yes')
			continue
		else:
			print('No')
			continue
	w = 1
	while w <= n:
		if (n - w) % b == 0:
			print('Yes')
			n = -1
			break
		else:
			w *= a
	if n != -1:
		print('No')


def solve(n, a, b):
	if n == 1:
		return True
	if b == 1:
		return True
	if a == 1:
		if n % b == 1:
			return True
		else:
			return False
	k = 0
	while a ** k <= n:
		m = n - a ** k
		if m % b == 0:
			return True
		k += 1
	return False
T = int(input())
for _ in range(T):
	(n, a, b) = map(int, input().split())
	if solve(n, a, b):
		print('Yes')
	else:
		print('No')


from collections import defaultdict
import sys, io, os
INP = sys.stdin.readline
inp = lambda : [*map(int, INP().encode().split())]
sinp = lambda : [*map(str, INP().split())]
out = sys.stdout.write

def main():
	for _ in range(inp()[0]):
		(n, a, b) = inp()
		if b == 1:
			print('Yes')
			continue
		if a == 1:
			if n % b != 1:
				print('No')
			else:
				print('Yes')
			continue
		check = 0
		fist = 1
		while fist <= n:
			if not (n - fist) % b:
				check = 1
			fist *= a
		if not check:
			print('No')
		else:
			print('Yes')

def SumOfExpOfFactors(a):
	fac = 0
	lis = SortedList()
	if not a & 1:
		lis.add(2)
	while not a & 1:
		a >>= 1
		fac += 1
	for i in range(3, int(a ** 0.5) + 1, 2):
		if not a % i:
			lis.add(i)
		while not a % i:
			a //= i
			fac += 1
	if a != 1:
		lis.add(a)
		fac += 1
	return (fac, lis)
div = [0] * 1000001

def NumOfDivisors(n):
	for i in range(1, n + 1):
		for j in range(i, n + 1, i):
			div[j] += 1

def primes1(n):
	sieve = [True] * (n // 2)
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i // 2]:
			sieve[i * i // 2::i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [2 * i + 1 for i in range(1, n // 2) if sieve[i]]

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

class Graph:

	def __init__(self):
		self.Graph = defaultdict(list)

	def addEdge(self, u, v):
		self.Graph[u].append(v)
		self.Graph[v].append(u)

	def DFSUtil(self, v, visited):
		visited.add(v)
		for neighbour in self.Graph[v]:
			if neighbour not in visited:
				self.DFSUtil(neighbour, visited)

	def DFS(self, v):
		visited = set()
		self.DFSUtil(v, visited)

	def BFS(self, s):
		visited = set()
		queue = []
		queue.append(s)
		visited.add(s)
		while queue:
			s = queue.pop(0)
			for i in self.Graph[s]:
				if i not in visited:
					queue.append(i)
					visited.add(i)

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
main()


import sys, os.path
from collections import *
from heapq import *
from copy import *
import math
mod = 10 ** 9 + 7
read = lambda : map(int, input().split())
inf = float('inf')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for t in range(int(input())):
	(n, a, b) = read()
	if b == 1:
		print('Yes')
	elif a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		t = []
		c = 1
		while c <= n:
			t.append(c)
			c *= a
		m = len(t)
		flag = 0
		for i in range(m):
			if (n - t[i]) % b == 0:
				flag = 1
				break
		if flag == 1:
			print('Yes')
		else:
			print('No')


import sys
import math as mt
input = sys.stdin.readline

def solution(n, a, b):
	tmp = 1
	if a == 1:
		if (n - 1) % b == 0:
			return 'Yes'
		else:
			return 'No'
	while tmp <= n:
		if (n - tmp) % b == 0:
			return 'Yes'
		tmp *= a
	return 'No'

def main():
	for _ in range(int(input())):
		print(solution(*map(int, input().split())))
main()


import os
import sys
from math import *
from collections import *
from itertools import *
from heapq import *
from bisect import *
from io import BytesIO, IOBase
from typing import overload

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 998244353
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]

def divisors(n):
	div = set()
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			div.add(i)
			div.add(n // i)
	return div
for _ in range(Int()):
	(n, a, b) = value()
	ans = 'NO'
	if a == 1:
		if (n - 1) % b == 0:
			ans = 'YES'
	else:
		x = 1
		while x <= n:
			if (n - x) % b == 0:
				ans = 'YES'
				break
			x *= a
	print(ans)


from math import *
from collections import *
from functools import *
from bisect import *
from itertools import *
from heapq import *
inf = float('inf')
ninf = -float('inf')
ip = input
alphal = 'abcdefghijklmnopqrstuvwxyz'
alphau = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
mod = 10 ** 9 + 7

def ipl():
	return list(map(int, ip().split()))

def ipn():
	return int(ip())

def ipf():
	return float(ip())

def ptrres(a):
	for i in a:
		print(i, end=' ')
	print()

def solve():
	(n, a, b) = ipl()
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
		return
	x = 1
	while x <= n:
		if n % b == x % b:
			print('YES')
			return
		x *= a
	print('NO')
t = ipn()
for _ in range(t):
	solve()


def ssv(x, n, m):
	for i in range(n):
		for j in range(m):
			try:
				if x[i][max(j - 1, 0)] == x[i][j]:
					lauda = 'lassan'
			except:
				lauda = 'lassan'
			try:
				if x[i][min(j + 1, m - 1)] == x[i][j]:
					lauda = 'lassan'
			except:
				lauda = 'lahsun'
			try:
				if x[max(0, i - 1)][j] == x[i][j]:
					lauda = 'lassan'
			except:
				lauda = 'lahsun'
			try:
				if x[min(n - 1, i + 1)][j] == x[i][j]:
					lauda = 'lassan'
			except:
				lauda = 'lahsun'

def ss(x):
	v = []
	v.append(x + x + 1)
	y = sum(v)
kk = int(input())
for lll in range(kk):
	x = list(map(int, input().split()))
	if x[0] == 1:
		print('YES')
		continue
	else:
		ss(x[0])
		o = 1
		fuxx = 0
		while o <= x[0]:
			if (x[0] - o) % x[2] == 0:
				print('YES')
				fuxx = 1
				break
			elif x[0] == o:
				print('YES')
				fuxx = 1
				break
			elif x[1] == 1:
				print('NO')
				fuxx = 1
				break
			o = o * x[1]
		if fuxx == 0:
			print('NO')


def ggwp(n, a, b):
	if a == 1:
		if (n - 1) % b == 0:
			return 'Yes'
		else:
			return 'No'
	op = 1
	while op <= n:
		if op % b == n % b:
			return 'Yes'
		op *= a
	return 'No'
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	print(ggwp(n, a, b))


from math import gcd

def solve(a, b, n):
	cur = 1
	if a == 1 and b == 1:
		return 'Yes'
	if n % b == 1:
		return 'Yes'
	if a == 1:
		return 'No'
	while cur <= n:
		rem = n - cur
		if rem % b == 0:
			return 'Yes'
		cur *= a
	return 'No'
for case in range(int(input())):
	(n, a, b) = list(map(int, input().split()))
	ans = solve(a, b, n)
	print(ans)


def solve(n, a, b):
	if a == 1:
		if b == 1:
			return 'Yes'
		if n % b == 1:
			return 'Yes'
		return 'No'
	cur = 1
	while cur <= n:
		left = n - cur
		if left % b == 0:
			return 'Yes'
		cur *= a
	return 'No'
for case in range(int(input())):
	(n, a, b) = list(map(int, input().split()))
	ans = solve(n, a, b)
	print(ans)


import itertools
import sys

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

def main():
	[t_n] = read_ints()
	for i_t in range(t_n):
		(n, a, b) = read_ints()
		can_be_represented = False
		passed = set()
		for m in itertools.count():
			temp_n = n - a ** m
			if temp_n < 0 or temp_n in passed:
				break
			passed.add(temp_n)
			if temp_n % b == 0:
				can_be_represented = True
				break
		if can_be_represented:
			print('Yes')
		else:
			print('No')
main()


from math import *
from collections import deque
from copy import deepcopy
import sys

def inp():
	return sys.stdin.readline().rstrip('\r\n')

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

def strmulti():
	return map(str, inp().split())

def lis():
	return list(map(int, inp().split()))

def lcm(a, b):
	return a * b // gcd(a, b)

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def stringlis():
	return list(map(str, inp().split()))

def out(var):
	sys.stdout.write(str(var))

def printlist(a):
	print(' '.join((str(a[i]) for i in range(len(a)))))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def google():
	t = int(inp())
	for T in range(t):
		print('Case #' + str(T + 1) + ': ', end='')
		solve()

def normal(x):
	if x == 0:
		t = int(inp())
	else:
		t = 1
	for T in range(t):
		solve()

def solve():
	(n, a, b) = multi()
	if b == 1:
		print('YES')
		return
	if a == 1:
		if floor((n - 1) / b) == ceil((n - 1) / b):
			print('YES')
		else:
			print('NO')
		return
	i = 0
	while a ** i <= n:
		if n % b == a ** i % b:
			print('YES')
			return
		i += 1
	print('NO')
	return
normal(0)


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	if n % b == 1 or b == 1:
		print('Yes')
	elif a == 1 or n < a:
		print('No')
	elif a % b == 0 and n % b == 0:
		print('Yes' if n >= a else 'No')
	else:
		check = 1
		c = 1
		while check <= n:
			if (n - check) % b == 0:
				print('Yes')
				c = 0
				break
			check *= a
		if c:
			print('No')


for _ in range(int(input())):
	(n, a, b) = map(int, input().strip().split())
	flag = 0
	s = 1
	if a == 1:
		if (n - 1) % b == 0:
			print('YES')
		else:
			print('NO')
	else:
		while s <= n:
			if (n - s) % b == 0:
				flag = 1
				break
			s = s * a
		if flag == 1:
			print('YES')
		else:
			print('NO')


import sys
input = sys.stdin.readline
t = int(input())
for you in range(t):
	l = input().split()
	n = int(l[0])
	a = int(l[1])
	b = int(l[2])
	if b == 1:
		print('Yes')
		continue
	if a == 1:
		if n % b == 1:
			print('Yes')
		else:
			print('No')
		continue
	x = 1
	poss = 0
	z = n % b
	for i in range(35):
		if x % b == z and x <= n:
			poss = 1
			break
		if x > n:
			break
		x = x * a
	if poss:
		print('Yes')
	else:
		print('No')


from math import log
from sys import stdin
input = stdin.readline

def f(n, a, b):
	factors = [1]
	t = 1
	if a != 1:
		while t <= n:
			factors.append(t)
			t *= a
	for i in factors:
		if abs(n - i) % b == 0:
			return 'Yes'
	return 'No'
for _ in range(int(input())):
	(n, a, b) = map(int, input().strip().split())
	print(f(n, a, b))


def gen_set(a, b, n):
	seed = 1
	while seed <= n:
		yield seed
		seed *= a

def check(num, a, b):
	for x in gen_set(a, b, num):
		if (num - x) % b == 0:
			return True
	return False

def solve():
	(n, a, b) = [int(x) for x in input().split()]
	if b == 1:
		return 'Yes'
	if a == 1:
		if (n - 1) % b == 0:
			return 'Yes'
		return 'No'
	if check(n, a, b):
		return 'Yes'
	return 'No'
for _ in range(int(input())):
	print(solve())


def solve():
	(n, a, b) = map(int, input().split())
	if b == 1 or n == 1:
		return True
	if a == 1:
		return (n - 1) % b == 0
	ap = 1
	while ap <= n:
		if (n - ap) % b == 0:
			return True
		ap *= a
	return False
for _ in range(int(input())):
	print('yes' if solve() else 'no')


for _ in range(int(input())):
	(s, a, b) = map(int, input().split())
	cnt = 1
	while True:
		if cnt > s:
			print('No')
			break
		if (s - cnt) % b == 0:
			print('Yes')
			break
		cnt *= a
		if a == 1:
			print('No')
			break


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

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

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if True else 100):
	(n, a, b) = map(int, input().split())
	if b == 1:
		print('Yes')
		continue
	if n <= a:
		if n % b == 1 or n == a:
			print('Yes')
		else:
			print('No')
		continue
	pos = False
	cur = 1
	if a == 1:
		print('YES' if n % b == 1 or b == 1 else 'NO')
		continue
	while cur <= 10 ** 9:
		if n % b == cur % b and n >= cur:
			pos = True
		cur *= a
	print('YES' if pos else 'NO')


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	ans = 'NO'
	for k in range(31):
		if n < a ** k:
			break
		if n % b == a ** k % b:
			ans = 'YES'
			break
	print(ans)


t = int(input())
for i in range(0, t):
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		ans = 0
		r = 1
		while r <= n:
			if (n - r) % b == 0:
				ans = 1
				break
			r = r * a
		if ans == 1:
			print('Yes')
		else:
			print('No')


import os, sys, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def readint():
	return int(input().decode())
t = readint()
for _ in range(t):
	(n, a, b) = [int(x) for x in input().decode().split(' ')]
	if a == 1:
		if (n - 1) % b:
			sys.stdout.write('No\n')
		else:
			sys.stdout.write('Yes\n')
		continue
	subtractfrom = 1
	ans = False
	while subtractfrom <= n:
		diff = n - subtractfrom
		if diff % b == 0:
			ans = True
			break
		subtractfrom *= a
	if ans:
		sys.stdout.write('Yes\n')
	else:
		sys.stdout.write('No\n')


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	count = 1
	flag = 0
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
			continue
		else:
			print('No')
			continue
	while count <= n:
		if (n - count) % b == 0:
			print('Yes')
			flag = 1
			break
		count *= a
	if flag == 0:
		print('No')


t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	seed = 1
	sol = False
	if a == 1:
		if (n - seed) % b == 0:
			sol = True
	else:
		while seed <= n:
			if (n - seed) % b == 0:
				sol = True
				break
			seed *= a
	print('Yes' if sol else 'No')


t = int(input())
while t:
	t -= 1
	(n, a, b) = map(int, input().split())
	if b == 1 or n == 1 or n % b == 1:
		print('Yes')
	else:
		a1 = a
		f = 0
		k = b
		k1 = -1
		if a != 1 and f != 1:
			while n >= a1:
				k = n - a1
				a1 *= a
				if k % b == 0:
					print('Yes')
					f = 1
					break
				k1 = k
			if f != 1:
				n1 = n
				while n % a == 0 and n > 1:
					n = n // a
				if n == 1:
					f = 1
				n = n1
		if f == 0:
			print('No')


import sys
input = sys.stdin.readline
from math import gcd
from collections import defaultdict

def lcm(a, b):
	return a * b // gcd(a, b)
t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
		continue
	s = set()
	x = 1
	while x <= n:
		s.add(x % b)
		x *= a
	for m in s:
		if (n - m) % b == 0:
			print('Yes')
			break
	else:
		print('No')


t = int(input())
for tests in range(t):
	(n, a, b) = [int(i) for i in input().split(' ')]
	sol = 'No'
	r = 1
	if a == 1:
		if (n - 1) % b == 0:
			sol = 'Yes'
	else:
		rem = n % b
		while r <= n:
			if r % b == rem:
				sol = 'Yes'
				break
			r *= a
	print(sol)


from sys import stdin

def get_ans(n, a, b):
	p = 1
	while p <= n:
		if b == 1 or n % b == p % b:
			print('Yes')
			return
		p *= a
	print('NO')
	return
t = int(stdin.readline())
for _ in range(t):
	(n, a, b) = map(int, stdin.readline().split())
	if a == 1:
		print('Yes' if n % b == 1 or b == 1 else 'NO')
	else:
		get_ans(n, a, b)


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		(n, a, b) = map(int, input().split(' '))
		done = 'NO'
		for x in range(50):
			if a ** x > int(10000000000.0):
				break
			if a ** x == n or ((n - a ** x) % b == 0 and n - a ** x >= 0):
				done = 'YES'
		print(done)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	(n, a, b) = [int(x) for x in input().split()]
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
		continue
	f = False
	curr = 1
	while curr <= n:
		if (n - curr) % b == 0:
			f = True
			break
		curr *= a
	if f:
		print('Yes')
	else:
		print('No')


from sys import stdin, setrecursionlimit, maxsize
input = stdin.readline
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	res = 0
	if a == 1:
		if (n - 1) % b == 0:
			res = 1
	else:
		x = 1
		while x <= n:
			if x % b == n % b:
				res = 1
				break
			x *= a
	print('Yes' if res else 'No')


def solve(x, a, b):
	if a == 1:
		if (x - 1) % b == 0:
			return 'Yes'
		return 'No'
	an = 1
	while an <= x:
		if (x - an) % b == 0:
			return 'Yes'
		an *= a
	return 'No'
t = int(input())
for i in range(t):
	(x, a, b) = map(int, input().split())
	print(solve(x, a, b))


def void():
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		i = 1
		valid = False
		while i <= n:
			if (n - i) % b == 0:
				valid = True
				break
			i *= a
		if valid:
			print('Yes')
		else:
			print('No')
for i in range(int(input())):
	void()


def in_set(n, a, b):
	if n == 1 or n % b == 1 or b == 1:
		return True
	x = 1
	while x <= n and a > 1:
		if x % b == n % b:
			return True
		x *= a
	return False
q = int(input())
for i in range(q):
	(n, a, b) = map(int, input().split())
	print('Yes' if in_set(n, a, b) else 'No')


import sys, math, bisect
from random import randint
inf = float('inf')
mod = 10 ** 9 + 7

def lcm(a, b):
	return int(a / math.gcd(a, b) * b)

def gcd(a, b):
	return int(math.gcd(a, b))

def tobinary(n):
	return bin(n)[2:]

def binarySearch(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def lowerBound(a, x):
	i = bisect.bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def upperBound(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a) + 1 and a[i - 1] == x:
		return i - 1
	else:
		return -1

def primesInRange(n):
	ans = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def primeFactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n = n // i
	if n > 2:
		factors.append(n)
	return factors

def isPrime(n, k=5):
	if n < 2:
		return True
	for i in range(0, k):
		a = randint(1, n - 1)
		if pow(a, n - 1, n) != 1:
			return False
	return True
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify
import string
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	flag = False
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		x = 0
		while pow(a, x) <= n:
			if (n - pow(a, x)) % b == 0:
				flag = True
				break
			else:
				x += 1
		if flag:
			print('Yes')
		else:
			print('No')


def solve(n, a, b):
	if a == 1:
		return 'Yes' if n % b == 1 or b == 1 else ' No'
	tmp = 1
	while tmp <= n:
		if (n - tmp) % b == 0:
			return 'Yes'
		tmp *= a
	return 'No'
for t in range(int(input())):
	(n, a, b) = map(int, input().split())
	print(solve(n, a, b))


from sys import stdin
input = stdin.readline
rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip()
YN = lambda x: print('YES') if x else print('NO')
mod = 10 ** 9 + 7
for _ in range(rn()):
	(n, a, b) = rns()
	if a == 1:
		YN((n - 1) % b == 0 or n == 1)
	else:
		root = a
		a = 1
		ans = False
		while a <= n:
			ans = ans or (n - a) % b == 0
			a *= root
		YN(ans or n == 1)


from sys import stdin, stdout
import sys
import math
import itertools
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)
t = int(stdin.readline().strip())
for j in range(1, t + 1):
	(n, a, b) = map(int, stdin.readline().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		t = 1
		while t <= n:
			if (n - t) % b == 0:
				print('Yes')
				break
			t = t * a
		else:
			print('No')


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	x = 1
	check = False
	while a != 1 and x <= n:
		y = (n - x) % b
		if y == 0:
			print('YES')
			check = True
			break
		x *= a
	if not check:
		while a != 1 and n % a == 0:
			n //= a
		if (n - 1) % b == 0:
			print('YES')
		else:
			print('NO')


import math
import heapq

def solve(n, a, b):
	if b == 1:
		return 'Yes'
	t = 1
	while t <= n:
		if t % b == n % b:
			return 'Yes'
		if a == 1:
			break
		t *= a
	return 'No'
T = int(input())
for t in range(T):
	(n, x, y) = list(map(int, input().split()))
	res = solve(n, x, y)
	print(res)


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	(n, a, b) = map(int, input().split())
	flg = False
	if b == 1:
		flg = True
	elif a == 1:
		if n % b == 1:
			flg = True
	else:
		temp = 1
		while n >= temp:
			if n % b == temp % b:
				flg = True
				break
			else:
				temp *= a
	if flg:
		print('Yes')
	else:
		print('No')


t = int(input())
while t:
	(n, x, y) = map(int, input().split())
	if x == 1:
		if (n - 1) % y == 0:
			print('Yes')
		else:
			print('No')
	else:
		p = 1
		flag = 0
		while p <= n:
			if (n - p) % y == 0:
				flag = 1
				break
			p *= x
		if flag == 1:
			print('Yes')
		else:
			print('No')
	t -= 1


t = int(input())
ans = []
for i in range(t):
	res = False
	(n, a, b) = map(int, input().split())
	a_pow = 1
	if a == 1:
		ans.append((n - a_pow) % b == 0)
	else:
		while a_pow <= n:
			if (n - a_pow) % b == 0:
				res = True
				break
			a_pow *= a
		ans.append(res)
for r in ans:
	if r:
		print('Yes')
	else:
		print('No')


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())

def solve_brute(n, a, b):
	dp = [0 for i in range(n + 1)]
	dp[1] = 1
	for i in range(1, n):
		if not dp[i]:
			continue
		if i + b <= n:
			dp[i + b] = True
		if a * i <= n:
			dp[a * i] = True
	return dp[n]

def solve(n, a, b):
	tmp = 1
	for k in range(61):
		if tmp > n:
			return False
		if (n - tmp) % b == 0:
			return True
		tmp *= a
while False:
	n = random.randint(1, 10)
	a = random.randint(1, 10)
	b = random.randint(1, 10)
	if solve(n, a, b) != solve_brute(n, a, b):
		print(n, a, b)
		exit()
for _ in range(int(input())):
	(n, a, b) = mi()
	print('Yes' if solve(n, a, b) else 'No')


t = int(input())
for i in range(t):
	inp = input().split(' ')
	n = int(inp[0])
	a = int(inp[1])
	b = int(inp[2])
	r = n % b
	s = 1
	flag = False
	if b == 1:
		flag = True
	elif a == 1:
		flag = r == 1
	else:
		while n > 0:
			if s == r:
				flag = True
				break
			s = s * a % b
			n = n // a
			if s == 1:
				break
	if flag:
		print('Yes')
	else:
		print('No')


from collections import deque
import heapq
from math import sqrt
import operator
from operator import itemgetter
import sys
import copy
inf_var = 0
if inf_var == 1:
	inf = open('input.txt', 'r')
else:
	inf = sys.stdin
input = inf.readline

def read_one_int():
	return int(input().rstrip('\n'))

def read_one_float():
	return float(input().rstrip('\n'))

def read_list_of_ints():
	res = [int(val) for val in input().rstrip('\n').split(' ')]
	return res

def read_str():
	return input().rstrip()

def main():
	tests = read_one_int()
	for _ in range(tests):
		(n, a, b) = read_list_of_ints()
		if n == 1 or b == 1:
			print('Yes')
			continue
		if a == 1:
			if (n - 1) % b:
				print('No')
			else:
				print('Yes')
			continue
		cur_m = 1
		res = 'No'
		while cur_m <= n:
			if n % b == cur_m % b:
				res = 'Yes'
				break
			cur_m *= a
		print(res)
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def scanf(datatype=str):
	return datatype(sys.stdin.readline().rstrip())

def printf(answer=''):
	return sys.stdout.write(str(answer) + '\n')

def prints(answer):
	return sys.stdout.write(str(answer) + ' ')

def map_input(datatype=str):
	return map(datatype, sys.stdin.readline().split())

def list_input(datatype=str):
	return list(map(datatype, sys.stdin.readline().split()))

def testcase(number: int, solve_function):
	for _ in range(number):
		printf(solve_function())

def solve():
	(n, a, b) = map_input(int)
	if a == 1:
		if (n - 1) % b == 0:
			return 'Yes'
		return 'No'
	term = 1
	while term <= n:
		if (n - term) % b == 0:
			return 'Yes'
		term *= a
	return 'No'
t = scanf(int)
testcase(t, solve)


def pam(n, a, b):
	if (n - 1) % b == 0:
		return 'Yes'
	if a == 1:
		return 'No'
	p = 1
	while p <= n:
		if (n - p) % b == 0:
			return 'Yes'
		p *= a
	return 'No'
for t in range(int(input())):
	(n, a, b) = map(int, input().split())
	print(pam(n, a, b))


def solve(n, a, b):
	if a == 1:
		if (n - 1) % b == 0:
			return True
		else:
			return False
	else:
		temp = 1
		while temp <= n:
			if (n - temp) % b == 0:
				return True
			temp *= a
		temp //= a
		return (n - temp) % b == 0
t = int(input())
while t:
	(n, a, b) = [int(k) for k in input().split()]
	ans = solve(n, a, b)
	if ans:
		print('Yes')
	else:
		print('No')
	t -= 1


from functools import lru_cache
import copy
import math
import sys
fin = None
fout = None
uabet = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
abet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

def start(filename):
	filename = filename.replace('.py', '')
	global fin
	global fout
	infile = filename + '.in'
	outfile = filename + '.out'
	fin = open(infile)
	fout = open(outfile, 'w')

def permutation(lst):
	if len(lst) == 0:
		return []
	if len(lst) == 1:
		return [lst]
	l = []
	for i in range(len(lst)):
		m = lst[i]
		remLst = lst[:i] + lst[i + 1:]
		for p in permutation(remLst):
			l.append([m] + p)
	return l

def subsets(x):
	retset = []
	if len(x) == 0:
		retset = [[]]
	else:
		first = x[-1]
		cop = x.copy()
		cop.remove(first)
		y = subsets(cop)
		retset.extend(copy.deepcopy(y))
		m = copy.deepcopy(y)
		for i in range(len(y)):
			k = m[0]
			m.remove(k)
			k.append(first)
			m.append(k)
		retset.extend(m.copy())
	return retset

class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def __str__(self):
		return str(self.x) + str(self.y)

	def __hash__(self):
		return hash(str(self))

	def __eq__(self, other):
		return self.x == other.x and self.y == other.y

class frac:

	def __init__(self, n, d):
		self.n = n
		self.d = d

	def __str__(self):
		return str(self.n) + '/' + str(self.d)

	def __hash__(self):
		return hash(str(self))

	def simp(self):
		div = math.gcd(self.n, self.d)
		self.n = self.n / div
		self.d = self.d / div

	def __eq__(self, other):
		return self.n / self.d == other.n / other.d

	def __lt__(self, other):
		return self.n / self.d < other.n / other.d

class Interval:

	def __init__(self, start, end):
		self.start = start
		self.end = end

	def __str__(self):
		return str(self.start) + str(self.end)

	def __hash__(self):
		return hash(str(self))

	def __eq__(self, other):
		return self.start == other.start and self.end == other.end

	def __lt__(self, other):
		return self.start < other.start

class Graph:

	def __init__(self, vertices):
		self.V = vertices
		self.graph = [[0 for column in range(vertices)] for row in range(vertices)]

	def minDistance(self, dist, sptSet):
		min = sys.maxsize
		min_index = -1
		for v in range(self.V):
			if dist[v] < min and sptSet[v] == False:
				min = dist[v]
				min_index = v
		if min_index == -1:
			for v in range(self.V):
				if not sptSet[v]:
					min_index = v
					break
		return min_index

	def dijkstra(self, src):
		dist = [sys.maxsize] * self.V
		dist[src] = 0
		sptSet = [False] * self.V
		for cout in range(self.V):
			u = self.minDistance(dist, sptSet)
			sptSet[u] = True
			for v in range(self.V):
				if self.graph[u][v] > 0 and sptSet[v] == False and (dist[v] > dist[u] + self.graph[u][v]):
					dist[v] = dist[u] + self.graph[u][v]
		return dist

def overlap(verl1, verl2):
	if verl1.end >= verl2.start:
		return True
	else:
		return False

def merge(verl1, verl2):
	retverl = Interval(min(verl1.start, verl2.start), max(verl1.end, verl2.end))
	return retverl

def changeBase(num, base):
	if base == 2:
		return '{0:b}'.format(num)
	power = math.floor(math.log(num, base))
	remainder = num
	end = []
	iter = list(range(power + 1))
	iter.reverse()
	for i in iter:
		if remainder >= base ** i:
			(q, r) = divmod(remainder, base ** i)
			end.append(q)
			remainder = r
		else:
			end.append(0)
	retlist = []
	for i in end:
		if i > 9:
			retlist.append(uabet[i - 10])
		else:
			retlist.append(i)
	retlist = map(str, retlist)
	return ''.join(retlist)

def prime(num):
	if num == 2:
		return True
	if num % 2 == 0:
		return False
	for i in range(2, math.ceil(num ** 0.5) + 1):
		if num % i == 0:
			return False
	return True

def solve(n, a, b):
	if a == 1:
		if n % b == 1 % b:
			return 'Yes'
		return 'No'
	x = 1
	while x <= n:
		if n % b == x % b:
			return 'Yes'
		x *= a
	return 'No'

def main():
	t = int(input())
	for i in range(t):
		(n, a, b) = map(int, input().split(' '))
		print(solve(n, a, b))
main()


t = int(input())
for i in range(t):
	y = 0
	(n, a, b) = map(int, input().split())
	l = []
	z = 0
	x = 1
	while z < 32 and x <= n:
		l.append(x)
		x *= a
		z += 1
	for j in range(len(l)):
		if n >= l[j] and (n - l[j]) % b == 0:
			y = 1
			print('Yes')
			break
	if y == 0:
		print('No')


n = int(input())

def check(n, a, b):
	if a == 1:
		if (n - 1) % b == 0:
			return 'Yes'
		else:
			return 'No'
	if b == 1:
		return 'Yes'
	x = 1
	while x <= n:
		if (n - x) % b == 0:
			return 'Yes'
		x *= a
	return 'No'
for m in range(n):
	l = list(map(int, input().split()))
	(n, a, b) = (l[0], l[1], l[2])
	print(check(n, a, b))


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	(N, A, B) = map(int, input().split())
	if N == 1 or B == 1:
		print('Yes')
		continue
	if A == 1:
		print('Yes' if (N - 1) % B == 0 else 'No')
		continue
	from collections import defaultdict
	d = {}
	a = 1
	while a <= N:
		if a % B not in d:
			d[a % B] = a
		a *= A
	if N % B not in d:
		print('No')
	else:
		print('Yes' if d[N % B] <= N else 'No')


t = int(input())
while t > 0:
	t -= 1
	v = input().split()
	n = int(v[0])
	a = int(v[1])
	b = int(v[2])
	if a == 1:
		if (n - 1) % b == 0:
			print('YES')
		else:
			print('NO')
	else:
		p = 1
		ok = False
		while not ok and p <= n:
			if p % b == n % b:
				ok = True
			p *= a
		if ok:
			print('YES')
		else:
			print('NO')


t = int(input())
for j in range(0, t):
	(n, a, b) = [int(x) for x in input().split()]

	def check(n, a, b):
		l = 1
		if a == 1:
			if (n - 1) % b == 0:
				return 'Yes'
			else:
				return 'No'
		while n >= l:
			if (n - l) % b == 0:
				return 'Yes'
			l *= a
		if n < l:
			return 'No'
	print(check(n, a, b))


from math import log
t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	(c, valid) = (1, 0)
	if a == 1:
		print('Yes' if (n - 1) % b == 0 else 'No')
		continue
	for i in range(int(log(n, a)) + 2):
		if c > n:
			break
		if (n - c) % b == 0:
			valid = 1
			break
		c *= a
	print('Yes' if valid else 'No')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	if a == 1 or b == 1:
		if a == 1:
			if (n - 1) % b == 0:
				print('Yes')
			else:
				print('No')
		else:
			print('Yes')
	else:
		c = n
		k = 0
		while c > 1:
			c = c // a
			k += 1
		t = 0
		for i in range(k + 5):
			rr = n
			if i == 0:
				if (n - 1) % b == 0:
					t = 1
					break
			else:
				rr -= a ** i
				if rr < 0:
					break
				if rr % b == 0:
					t = 1
					break
		if t:
			print('Yes')
		else:
			print('No')


import functools
t = int(input())

def deal(mem, n, a, b):
	print(n)
	if n in mem:
		return mem[n]
	if n == 1 or b == 1 or (n - 1) % b == 0:
		return True
	if a == 1:
		return False
	res = False
	if n % a == 0:
		res |= deal(mem, n // a, a, b)
	if n > b:
		res |= deal(mem, n - b, a, b)
	mem[n] = res
	return res
for i in range(t):
	items = input().split(' ')
	n = int(items[0])
	a = int(items[1])
	b = int(items[2])
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
		continue
	else:
		x = 1
		while 1:
			if (n - x) % b == 0:
				print('Yes')
				break
			x *= a
			if x > n:
				print('No')
				break
		continue


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)

def ip():
	return int(input())

def sp():
	return str(input().rstrip())

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

def msp():
	return map(str, input().split().rstrip())

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

def lmsp():
	return list(map(str, input().split().rstrip()))
t = ip()
while t:
	t -= 1
	(n, a, b) = mip()
	if a == 1:
		print('No' if (n - 1) % b else 'Yes')
		continue
	k = 1
	f = False
	while k <= n:
		if k % b == n % b:
			f = True
			break
		k *= a
	print('Yes' if f else 'No')


def check(n, a, b):
	if b == 1:
		return True
	if a == 1:
		return n % b == 1
	x = 1
	while x <= n:
		if x % b == n % b:
			return True
		x *= a
	return False

def main():
	t = int(input())
	for _ in range(t):
		(n, a, b) = [int(word) for word in input().split()]
		if check(n, a, b):
			print('Yes')
		else:
			print('No')
main()


def solve():
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('YES')
		else:
			print('NO')
	else:
		curr = 1
		flag = 0
		while curr <= n:
			if curr % b == n % b:
				flag = 1
				break
			curr *= a
		if flag == 1:
			print('YES')
		else:
			print('NO')
tests = int(input())
for _ in range(tests):
	solve()


import sys
from sys import stdout
input = lambda : sys.stdin.readline().strip()
P = lambda : list(map(int, input().split()))
from math import factorial as f, gcd
from collections import deque, defaultdict as dd, Counter as C
from heapq import heapify, heappop, heappush, heappushpop, heapreplace, merge
from random import randint, choice, sample
import time
mod = 10 ** 9 + 7
a = ord('a')
start = time.time()

def fast_exp(x, exp):
	ans = 1
	base = x
	while exp:
		if exp & 1:
			ans *= base
		base *= base
		base %= mod
		ans %= mod
		exp >>= 1
	return ans

def countBits(n):
	count = 0
	while n:
		count += n & 1
		n >>= 1
	return count

def submasks(n):
	org = n
	while n:
		yield n
		n = n - 1 & org

def d2k(d, k):
	mapping = '0123456789ABCDEF'
	res = []
	while d != 0:
		res.append(d % k)
		d //= k
	return res[::-1]

def solve():
	(n, a, b) = P()
	if a == 1:
		print('Yes' if (n - 1) % b == 0 else 'No')
	else:
		curr = 1
		while curr <= n:
			if (n - curr) % b == 0:
				print('Yes')
				return
			curr *= a
		print('No')
tc = int(input())
for t in range(1, tc + 1):
	solve()


import sys
import math, statistics, random

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def N():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

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

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def void():
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		i = 1
		valid = False
		while i <= n:
			if (n - i) % b == 0:
				valid = True
				break
			i *= a
		if valid:
			print('Yes')
		else:
			print('No')
for i in range(int(input())):
	void()


for _ in range(int(input())):
	(n, a, b) = [int(x) for x in input().split()]
	if a == 1:
		if (n - 1) % b == 0:
			print('YES')
		else:
			print('NO')
	else:
		x = 1
		ch = True
		while x <= n:
			if (n - x) % b == 0:
				ch = False
				break
			x *= a
		if ch:
			print('NO')
		else:
			print('YEs')


import sys
import math
mod = 10 ** 9 + 7
LI = lambda : [int(k) for k in input().split()]
input = lambda : sys.stdin.readline().rstrip()
IN = lambda : int(input())
S = lambda : input()
r = range
for t in r(IN()):
	(n, a, b) = LI()
	if a == 1:
		n -= 1
		if n % b == 0:
			print('YES')
		else:
			print('NO')
		continue
	x = 1
	while x <= n:
		if (n - x) % b == 0:
			print('YES')
			break
		x *= a
	else:
		print('NO')


t = int(input())
for i in range(t):
	w = input().split()
	n = int(w[0])
	a = int(w[1])
	b = int(w[2])
	if a == 1:
		if (n - 1) % b == 0:
			print('YES')
		else:
			print('NO')
	else:
		t = 1
		flag = 0
		while t <= n:
			if t % b == n % b:
				flag = 1
				break
			t = t * a
		if flag == 1:
			print('YES')
		else:
			print('NO')


from sys import stdin
for _ in range(int(stdin.readline())):
	(n, a, b) = map(int, stdin.readline().split())
	temp = 1
	flag = False
	while temp <= n:
		if (n - temp) % b == 0:
			flag = True
			break
		temp *= a
		if a == 1:
			break
	print('Yes') if flag else print('No')


import sys
input = sys.stdin.readline

def print(x, end='\n'):
	sys.stdout.write(str(x) + end)

def get_int():
	return int(input())

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

def get_char_list():
	s = input()
	return list(s[:len(s) - 1])

def get_tuple_ints():
	return tuple(map(int, input().split()))

def print_iterable(p):
	print(' '.join(map(str, p)))

def main():
	t = get_int()
	for i in range(t):
		(n, a, b) = get_tuple_ints()
		if a == 1:
			if (n - 1) % b == 0:
				print('Yes')
			else:
				print('No')
		else:
			t = 1
			flag = 0
			while t <= n:
				if t % b == n % b:
					flag = 1
					break
				t = t * a
			if flag == 1:
				print('Yes')
			else:
				print('No')
main()


import sys
input = sys.stdin.readline

def solve():
	(n, a, b) = map(int, input().split())
	c = 1
	while c <= n:
		if (n - c) % b == 0:
			print('Yes')
			return
		if a == 1:
			break
		c *= a
	print('No')
for i in range(int(input())):
	solve()


t = int(input())

def solve(n, a, b):
	if a == 1:
		if (n - 1) % b == 0:
			return 'Yes'
		else:
			return 'No'
	ans = 'No'
	ax = 1
	while ax <= n:
		if (n - ax) % b == 0:
			ans = 'Yes'
			break
		ax *= a
	return ans
for _ in range(t):
	(n, a, b) = map(int, input().split())
	print(solve(n, a, b))


def solve(n, a, b):
	if b == 1:
		return 'Yes'
	if a == 1:
		if n % b == 1:
			return 'Yes'
		else:
			return 'No'
	x = 1
	while x <= n:
		if n % b == x % b:
			return 'Yes'
		x = x * a
	return 'No'
N = int(input())
for _ in range(N):
	a = list(map(int, input().split(' ')))
	print(solve(a[0], a[1], a[2]))


def solve(n, a, b):
	power = a
	while power <= n:
		x = n - power
		if x % b == 0:
			return 'Yes'
		power *= a
	return 'No'
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b != 0:
			print('No')
		else:
			print('Yes')
	elif (n - 1) % b == 0:
		print('Yes')
	else:
		print(solve(n, a, b))


for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	temp = 1
	check = False
	while n >= temp:
		if (n - temp) % b == 0:
			check = True
		if a != 1:
			temp *= a
		else:
			break
	if check:
		print('Yes')
	else:
		print('No')


def prb(n, a, b):
	if a == 1:
		if (n - 1) % b == 0:
			return 'Yes'
		else:
			return 'No'
	t = 1
	while t <= n:
		if (n - t) % b == 0:
			return 'Yes'
		t *= a
	return 'No'
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	print(prb(n, a, b))


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
from collections import Counter
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10001)]
prime[0] = prime[1] = False

def SieveOfEratosthenes(n=10000):
	p = 2
	c = 0
	while p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				prime[i] = False
		p += 1

class DSU:

	def __init__(self, R, C):
		self.par = range(R * C + 1)
		self.rnk = [0] * (R * C + 1)
		self.sz = [1] * (R * C + 1)

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return
		if self.rnk[xr] < self.rnk[yr]:
			(xr, yr) = (yr, xr)
		if self.rnk[xr] == self.rnk[yr]:
			self.rnk[xr] += 1
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]

	def size(self, x):
		return self.sz[self.find(x)]

	def top(self):
		return self.size(len(self.sz) - 1) - 1

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return math.gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = math.gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = math.gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[n - 1]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = arr[mid]
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = -1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid][0] >= key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
t = 1
t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	if (n - 1) % b == 0:
		print('Yes')
		continue
	if a == 1:
		print('No')
		continue
	curr = 1
	while curr < n:
		if not (n - curr) % b:
			curr = n
			break
		curr *= a
	if curr == n:
		print('Yes')
	else:
		print('No')


import sys
input = lambda : sys.stdin.readline().rstrip()
print = sys.stdout.write
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	result = False
	x = 0
	vt = set()
	while True:
		value = n - a ** x
		if value in vt:
			break
		vt.add(value)
		if value < 0:
			break
		if value % b == 0:
			result = True
			break
		x += 1
	if result:
		print('Yes\n')
	else:
		print('No\n')


t = int(input())
while t != 0:
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		i = 1
		d = True
		while i <= n:
			if (n - i) % b == 0:
				d = False
				break
			i *= a
		if not d:
			print('Yes')
		else:
			print('No')
	t -= 1


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('YES')
		else:
			print('NO')
		continue
	t = 1
	flag = 0
	while t <= n:
		if (n - t) % b == 0:
			flag = 1
			break
		t = t * a
	if flag:
		print('YES')
	else:
		print('NO')


def solucion(n, a, b):
	sol = 'No'
	if a == 1:
		if (n - 1) % b == 0:
			sol = 'Yes'
	else:
		pot = 1
		while pot <= n:
			if pot % b == n % b:
				sol = 'Yes'
				break
			pot = pot * a
	return sol
t = int(input())
resp = []
for i in range(t):
	line = input().split()
	n = int(line[0])
	a = int(line[1])
	b = int(line[2])
	resp.append(solucion(n, a, b))
for i in resp:
	print(i)


import sys, os, io
from sys import stdin, stdout
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import bisect
import math
input = stdin.readline
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

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

def ii():
	return int(input())

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

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def power_set(L):
	cardinality = len(L)
	n = 2 ** cardinality
	powerset = []
	for i in range(n):
		a = bin(i)[2:]
		subset = []
		for j in range(len(a)):
			if a[-j - 1] == '1':
				subset.append(L[j])
		powerset.append(subset)
	powerset_orderred = []
	for k in range(cardinality + 1):
		for w in powerset:
			if len(w) == k:
				powerset_orderred.append(w)
	return powerset_orderred

def fastPlrintNextLines(a):
	print('\n'.join(map(str, a)))

def sortByFirstAndSecond(A):
	A = sorted(A, key=lambda x: x[0])
	A = sorted(A, key=lambda x: x[1])
	return list(A)

def dfs(node, vis, adj, lis):
	lis.append(node)
	vis[node] = 1
	for i in adj[node]:
		if vis[i] == 0:
			dfs(i, vis, adj, lis)

def dfsOfGraph(n, adj):
	lis = []
	vis = [0] * (n + 1)
	for i in range(1, n + 1):
		if vis[i] == 0:
			dfs(i, vis, adj, lis)
	return lis

def bfsOfGraph(n, adj):
	vis = [0] * (n + 1)
	lis = []
	for i in range(1, n + 1):
		if vis[i] == 0:
			queue = [i]
			vis[i] = 1
			while len(queue) > 0:
				node = queue.pop(0)
				lis.append(node)
				for j in adj[node]:
					if vis[j] == 0:
						queue.append(j)
						vis[j] = 1
	return lis
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, a, b) = mi()
	if a == 1:
		if (n - 1) % b == 0:
			return 'Yes'
		return 'No'
	x = 0
	while pow(a, x) <= n:
		if (n - pow(a, x)) % b == 0:
			return 'Yes'
		x += 1
	return 'No'
t = ii()
for _ in range(t):
	res = solve()
	print(res)


t = int(input())
T = []
for i in range(t):
	T.append(tuple(map(int, input().split(' '))))
for testCase in T:
	(n, a, b) = testCase
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		m = 1
		flag = 0
		while m <= n:
			if m % b == n % b:
				flag = 1
				break
			m *= a
		if flag:
			print('Yes')
		else:
			print('No')


import math
import sys
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

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

def map_inp(v_type):
	return map(v_type, inp().split())

def list_inp(v_type):
	return list(map_inp(v_type))
for _ in range(int(inp())):
	(n, a, b) = map_inp(int)
	if a == 1:
		if n % b == 1 or b == 1:
			print('Yes')
		else:
			print('No')
	elif b == 1:
		print('Yes')
	elif n % b == 1:
		print('yes')
	else:
		ans = 'No'
		r = 1
		while r <= n:
			if n % b == r % b:
				ans = 'Yes'
				break
			r *= a
		print(ans)


def solve():
	(n, a, b) = map(int, input().split())
	ap = 1
	if a == 1 and n == 1:
		return 'Yes'
	if a == 1 and (n - 1) % b == 0:
		return 'Yes'
	if a == 1 and (n - 1) % b != 0:
		return 'No'
	while True:
		if ap > n:
			return 'No'
		rem = n - ap
		if rem % b == 0:
			return 'Yes'
		ap = ap * a
t = int(input())
for _ in range(t):
	print(solve())


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline
	for _ in range(int(input())):
		(N, a, b) = map(int, input().split())
		if a == 1:
			if (N - 1) % b == 0:
				print('Yes')
			else:
				print('No')
		else:
			ok = 0
			for k in range(40):
				if a ** k > N:
					break
				M = N - a ** k
				if M % b == 0:
					ok = 1
					break
			if ok:
				print('Yes')
			else:
				print('No')
main()


IP = lambda : list(map(int, input().split()))
IP = lambda : list(map(int, input().split()))
for i in range(int(input())):
	(n, a, b) = IP()
	if a == 1:
		print(('YES', 'NO')[(n - 1) % b != 0])
		continue
	ret = 1
	while ret <= n:
		if (n - ret) % b == 0:
			print('YES')
			break
		ret *= a
	else:
		print('NO')


t = int(input())
for u in range(t):
	(n, a, b) = map(int, input().split())
	if a != 1:
		s = 1
		f = 0
		while s <= n:
			if n % b == s % b:
				f = 1
				break
			s *= a
		if f == 1:
			print('Yes')
		else:
			print('No')
	elif (n - 1) % b == 0:
		print('Yes')
	else:
		print('No')


def solve():
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			return 'YES'
		return 'NO'
	poww = 1
	while poww <= n:
		if poww % b == n % b:
			return 'YES'
		poww *= a
	return 'NO'
t = int(input())
for _ in range(t):
	ans = solve()
	print(ans)


def solve(n, a, b):
	cur = 1
	if a > 1:
		while cur <= n and (n - cur) % b != 0:
			cur *= a
	if (n - cur) % b == 0 and cur <= n:
		print('Yes')
	else:
		print('No')
t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	solve(n, a, b)


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	possible = False
	cur = 1
	while cur <= n:
		if cur % b == n % b:
			possible = True
			break
		cur *= a
		if a == 1:
			break
	print('YES' if possible else 'NO')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
	else:
		i = 1
		flag = 1
		while i <= n:
			if (n - i) % b == 0:
				flag = 0
				print('Yes')
				break
			i *= a
		if flag:
			print('No')


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	m = n % b
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
		continue
	x = 1
	while x <= n:
		if x % b == m:
			print('Yes')
			break
		x *= a
	else:
		print('No')


ttt_ = int(input())
for __t in range(ttt_):
	(n, a, b) = map(int, input().split())
	if b == 1 or n == 1:
		print('Yes')
	else:
		k = 1
		if a == 1:
			if n % b == 1:
				n = 1
			else:
				n = 0
		while k <= n:
			if (n - k) % b == 0:
				n = 1
				break
			else:
				k = k * a
		if n == 1:
			print('Yes')
		else:
			print('No')


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

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

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('0')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def solve():
	for _ in range(1, ii() + 1):
		(n, a, b) = mi()
		x = [1, a]
		for i in range(30):
			x.append(x[-1] * a)
			if x[-1] > 1000000000.0:
				break
		n1 = len(x)
		ok = True
		for i in range(n1):
			if n % x[i] == 0:
				n2 = n // x[i]
				for j in range(n1):
					if n2 >= x[j] and (n2 - x[j]) % b == 0:
						print('YES')
						ok = False
						break
			if ok == False:
				break
		if ok:
			print('NO')
if file:
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


list_ans = []
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	s = 1
	if a == 1:
		if (n - 1) % b == 0:
			list_ans.append('Yes')
		else:
			list_ans.append('No')
	else:
		while s <= n:
			if (n - s) % b == 0:
				list_ans.append('Yes')
				break
			else:
				s *= a
		else:
			list_ans.append('No')
print(*list_ans, sep='\n')


t = int(input())
while t:
	t -= 1
	(n, a, b) = map(int, input().split())
	i = 0
	f = 0
	if b == 1:
		print('Yes')
		continue
	if a == 1:
		if (n - 1) % b == 0:
			print('Yes')
		else:
			print('No')
		continue
	while pow(a, i) <= n:
		k = n - pow(a, i)
		f |= k % b == 0
		i += 1
	if f:
		print('Yes')
	else:
		print('No')