import sys
input = sys.stdin.readline
t = int(input())
mx = 140
for _ in range(t):
    a,b,c = map(int,input().split())
    l = [0] * mx
    
    A = a
    for i in range(1,mx):
        l[i] = l[i-1]
        while(A % c == 0):
            A//=c
            l[i]+=1
        A*=a
    
    p = 1
    for i in range(mx):
        if(l[i]*p > l[p]*i):
            p = i
    
    print(l[p]*b//p%998244353)