t=int(input())
for _ in range(t):
    a,b,c=map(int,input().split())
    d=1
    ans=0
    cnt=0
    for i in range(1,140):
        d*=a
        while d%c==0:
            cnt+=1
            d//=c
        ans=max(ans,cnt*b//i)
    print(ans%998244353)