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