import sys
import math

T=int(input())
for t in range(T):
	A,B,C=map(int,input().strip().split(" "))
	
	p = 0
	q = 1
	for i in range(1,136):
		A2=A**i
		num = 0
		while A2 % C == 0:
			num += 1
			A2 /= C
		# if p/q < num / i
		if p * i < num * q:
			p = num
			q = i
		
	
	print(p * B // q % 998244353)