"""
① n十分大でM^{B^n}=1 mod p が必要
→　ord(M)|B^n が必要
→　ord(M)≦p≦B≦10^6なのでn≦log2(10^6)≦20まで調べれば十分。最小のnをn_pとおく
② ord_p(B)=e、B=B'p^eとおく。M^{B^n}=(M^{B'^n})^{p^{en}}であり、
一般に(1+xp^n)^p=1+x'p^{n+1}である（二項定理より）ことと、
n_pの定義からn≧n_pでM^{B'^n}=1 mod pであることから、
n≧n_pでM^{B^n}=1 mod p^{en}
③ あるn≧N+1に対してaが存在してM^{B^n}=1+aB^n mod B^{n+N}となるなら、
そのaで任意のn'≧nに対しても成り立つ（二項定理より）
④ ②③とCRTよりmax(max(n_p),N+1)乗すれば十分。max(n_p)≦20、N≦log2(10^6)<20なので高々20乗
→　実際に計算すれば良い(?)

実はmax(max(n_p),N)乗でも正しい。このとき仮定を満たさないのは③だけだが、
実際に③が成り立たないためにはBが偶数かつaが奇数であることが必要であり、
②の最後の式がmod p^{en+1}で成り立っていることを思い出すとそのようなことはあり得ない。
"""

from functools import cache
@cache
def factor(n):
	# return {p:prime | n%p==0}
	ret=[]
	for p in range(2,n+1):
		if p*p>n: break
		if n%p==0:
			ret.append(p)
			while n%p==0: n//=p
	if n!=1: ret.append(n)
	return ret

def g(m,b,p):
	# return min{n | m**(b**n)%p==1}
	crr=m%p
	for n in range(22):
		if crr==1: break
		crr=pow(crr,b,p)
	return n

def solve(B,N,M):
	primes=factor(B)
	e=max(g(M,B,p) for p in primes)
	if e==21: return -1
	E=max(N,e)
	temp=pow(M,B**E,B**(E+N))
	return temp//(B**E)

T=int(input())
for _ in range(T):
	print(solve(*map(int,input().split())))