LIM_M = 10**6
LIM_K = 10
MOD = 998244353

acc_jordan: list[list[int]]

def prev():
    global acc_jordan

    # spf[i] := i の最小素因数
    spf = [0] * (LIM_M + 1)
    primes = []
    for i in range(2, LIM_M + 1):
        if spf[i] == 0:
            spf[i] = i
            primes.append(i)
        for p in primes:
            v = i * p
            if v > LIM_M or p > spf[i]:
                break
            spf[v] = p

    # jordan[k][n] := Jordan のトーシェント関数 J_k(n)
    jordan = [[1] * (LIM_M + 1) for _ in range(LIM_K + 1)]
    for k in range(1, LIM_K + 1):
        for n in range(2, LIM_M + 1):
            m = n // spf[n]
            if m % spf[n] == 0:
                jordan[k][n] = jordan[k][m] * pow(spf[n], k, MOD) % MOD
            else:
                jordan[k][n] = jordan[k][m] * (pow(spf[n], k, MOD) - 1) % MOD

    # Jordan のトーシェント関数の累積和
    acc_jordan = [[0] * (LIM_M + 2) for k in range(LIM_K + 1)]
    for k in range(1, LIM_K + 1):
        for n in range(LIM_M + 1):
            acc_jordan[k][n + 1] = (acc_jordan[k][n] + jordan[k][n]) % MOD

def solve():
    N, M, K = [int(s) for s in input().split()]
    ans = 0

    l = 1
    while l <= M:
        q = M // l
        r = M // q
        sum_j = (acc_jordan[K][r + 1] - acc_jordan[K][l]) % MOD
        ans = (ans + sum_j * pow(q, N, MOD)) % MOD
        l = r + 1

    print(ans)

T = int(input())
prev()
for _ in range(T):
    solve()