MOD = 998244353


def solve():
    A, B, C = map(int, input().split())
    if pow(A, B, C) != 0:
        print(0)
        return
    x = A % C
    l = [x]
    while x:
        x *= x
        x %= C
        l.append(x)
    t = 0
    x = 1
    for i in reversed(range(len(l) - 1)):
        y = x * l[i] % C
        if y:
            t |= 1 << i
            x = y
    print(B // (t + 1) % MOD)


for _ in range(int(input())):
    solve()