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