import math
T=int(input())
for _ in range(T):
	a,b,c=map(int,input().split())
	A=1
	ans=0
	for i in range(1,500):
		A*=a
		X=A
		t=0
		while X%c==0:
			X//=c
			t+=1
		ans=max(ans,t*b//i)
	print(ans%998244353)