exec("def gcd(a,b):\n if not a:return b\n"+" if not(b:=b%a):return a\n if not(a:=a%b):return b\n"*300+" return gcd(a,b)") for i in range(int(input())): a,b,c=map(int,input().split()) r=0 while a%c<1:a//=c;r+=1 r*=b;x=gcd(a,c) X=0;a=1 while b: if b&1: r+=X a=gcd(a*x,c) if a==c:r+=1;a=1 X+=X x=gcd(x*x,c) if x==c:x=1;X+=1 b>>=1 print(r%998244353)