R=range
J=lambda:map(int,input().split())
L=10**5
P=[]
C=[0]*L
for i in R(2,L):
	if C[i]<1:
		P+=[i];j=i*i
		while j<L:C[j],j=1,j+i
def m(n,d):
	global r
	if r[1]<1or r[0]*d>n*r[1]:r=[n,d]
def M(n,d):
	global s
	if s[0]*d<n*s[1]:s=[n,d]
for t in R(sum(J())):
	A,B,C=J()
	r=[0,0]
	for p in P:
		v=w=0
		while C%p<1:v+=1;C//=p
		while A%p<1:w+=1;A//=p
		m(w,v)
	c=0
	D=1
	if C>1:
		s=[0,1]
		for p in R(1,8):
			D*=A
			while D%C<1:c+=1;D//=C
			M(c,p)
		m(*s)
	print(B*r[0]//r[1]%998244353)