import sys
sys.setrecursionlimit(1000001)

T = int(input())
for _ in range(T):
    def solve(A, B, C, ans):
        # print(A, B, C)
        # 何乗まで増やせば割り切れるか、二分探索
        if pow(A, B, C) != 0:
            return ans
        elif A % C == 0:
            times = 0
            A_cp = A
            while A_cp % C == 0:
                A_cp //= C
                times += 1
            ans += times * B
            return solve(A_cp, B, C, ans)
        else:
            ng = 0
            ok = B + 1
            while ok - ng > 1:
                mid = (ok + ng) // 2
                if pow(A, mid, C) == 0:
                    ok = mid
                else:
                    ng = mid
            ans += B // ok
            
            rem = pow(A, ok, C * C)
            return solve(rem // C, B // ok, C, ans)

    a, b, c = map(int, input().split())
    print(solve(a, b, c, 0) % 998244353)