MOD = 998244353
N = 400
dp = [[0 for _ in range(1<<12)] for _ in range(N+3+1)]
dp[1][0] = 1
for i in range(1,N+1+1):
    for j in range(1<<12):
        k0 = -1
        for k in range(12):
            if (j>>k)&1==0:
                k0 = k
                break
        if k0<0 or k0>=4:
            jn = j>>4
            dp[i+1][jn] = (dp[i+1][jn]+dp[i][j])%MOD
            continue
        r = k0%4
        if r>=1 and (j>>k0+4)&1==0 and (j>>k0+8)&1==0 and (j>>k0+3)&1==0:
            jn = j|(1<<k0)|(1<<(k0+4))|(1<<(k0+8))|(1<<(k0+3))
            dp[i][jn] = (dp[i][jn]+dp[i][j])%MOD
        if r>=1 and(j>>k0+4)&1==0 and (j>>k0+3)&1==0 and r<3 and (j>>k0+5)&1==0:
            jn = j|(1<<k0)|(1<<(k0+4))|(1<<(k0+3))|(1<<(k0+5))
            dp[i][jn] = (dp[i][jn]+dp[i][j])%MOD
        if r<3 and (j>>k0+4)&1==0 and (j>>k0+5)&1==0 and (j>>k0+8)&1==0:
            jn = j|(1<<k0)|(1<<(k0+4))|(1<<(k0+5))|(1<<(k0+8))
            dp[i][jn] = (dp[i][jn]+dp[i][j])%MOD
        if r<2 and (j>>k0+1)&1==0 and (j>>k0+2)&1==0 and (j>>k0+5)&1==0:
            jn = j|(1<<k0)|(1<<(k0+1))|(1<<(k0+2))|(1<<(k0+5))
            dp[i][jn] = (dp[i][jn]+dp[i][j])%MOD
T = int(input())
for _ in range(T):
    N = int(input())
    print(dp[4*N+1][0])