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