MOD=998244353
N=9

pows=[]
for n in range(11):
    a=[1]
    for i in range(601):
        a.append(a[-1]*n%MOD)
    pows.append(a)

def solvesub(W,H,X):
    ans=0
    for min_e in range(min(X+1,N+1)):
        for max_e in range(min_e,min(X+1,N+1)):
            if H==2 and not (min_e==0 and max_e==0):
                continue
            if H==2:
                pat_e=1
            else:
                d=max_e-min_e+1
                pat_e=pows[d][H//2-1]-2*pows[d-1][H//2-1]+pows[max(0,d-2)][H//2-1]
                pat_e%=MOD
            for min_o in range(min(X+1,N+1)):
                for max_o in range(min_o, N+1):
                    pat_o=pows[max_o-min_o+1][H//2]-2*pows[max_o-min_o][H//2]+pows[max(0,max_o-min_o-1)][H//2]
                    pat_o%=MOD
                    for a00 in range(min(X+1,N+1)):
                        upper_o=min(X-a00-max_o,N)
                        lower_o=max(X-a00-N-min_o,0)
                        upper_e=min(a00+min_o,N)
                        lower_e=max(-N+a00+max_o,0)
                        if H>=3:
                            upper_o=min(upper_o,N-a00+min_e)
                            lower_o=max(lower_o,-a00+max_e)
                            upper_e=min(upper_e,N+a00-max_e)
                            lower_e=max(lower_e,a00-min_e)
                        if upper_o-lower_o<0 or (W>2 and upper_e-lower_e<0):
                            continue
                        add=pows[upper_o-lower_o+1][W//2]*pows[upper_e-lower_e+1][W//2-1]%MOD*pat_e%MOD*pat_o%MOD
                        ans=ans+add
                        if ans>=MOD:
                            ans-=MOD
    print(ans)

def solve(W,H,X):
    if W%3>H%3:
        W,H=H,W
    if (W%3==0 and H%3==0) or (W%3==0 and H%3==1) or (W%3==1 and H%3==1):
        print(int(X<=N))
    elif W%3==0 and H%3==2:
        d=min(N,X)-max(0,X-N)+1
        d=max(0,d)
        print(pow(d,W//3,MOD))
    elif W%3==1 and H%3==2:
        d=min(N,X)-max(0,X-N)+1
        d=max(0,d)
        print(pow(d,(W+2)//3,MOD))
    elif W%3==2 and H%3==2:
        solvesub((W+1)//3*2,(H+1)//3*2,X)
    else:
        raise Exception

def run():
    T=int(input())
    for t in range(T):
        W,H,X=map(int,input().split())
        solve(W,H,X)
run()