mod = 998244353
def mat_mul(A, B, f = 1): #行列同士と行列ベクトルの積を計算
    n = len(A) 
    if f: #modの計算を行うか分岐
        global mod
        if isinstance(B[0], list): #行列同士の積か分岐
            C = [[0 for _ in range(n)] for _ in range(n)]
            for y in range(n):
                for x in range(n):
                    for d in range(n):
                        C[y][x] += A[y][d] * B[d][x] % mod
                        C[y][x] %= mod
            return C
        else:
            C = [0 for _ in range(n)]
            for y in range(n):
                for x in range(n):
                    C[y] += A[y][x] * B[x] % mod
                    C[y] %= mod
            return C
    else:
        if isinstance(B[0], list):
            C = [[0 for _ in range(n)] for _ in range(n)]
            for y in range(n):
                for x in range(n):
                    for d in range(n):
                        C[y][x] += A[y][d] * B[d][x]
            return C
        else:
            C = [0 for _ in range(n)]
            for y in range(n):
                for x in range(n):
                    C[y] += A[y][x] * B[x]
            return C
def pow_mat(M, B, n): #行列の累乗（M = 正規行列、 B = 遷移行列）
    while n:
        if n & 1:
            M = mat_mul(B, M)
        B = mat_mul(B, B)
        n >>= 1
    return M

def main():
    n = int(input())
    I = {1: 0, -1: 1, 2: 2, -2: 3, 4: 4, -4: 5, -8: 6}
    A = [1, -1, 2, -2, 4, -4, -8]
    B = [1, -1, 2, -2]
    M = [[0] * 9 for _ in range(9)]
    for y in range(7):
        a = A[y]
        for b in B:
            if a == -8 and abs(b) == 2:
                continue
            c = a * b
            if c == 8:
                idx = 7
            else:
                idx = I[c]
            M[idx][y] += 1
    C = [0, 0, 1, 1, 0, 0, 0, 1, 1]
    for y in range(9):
        M[y][7] = C[y]
        M[y][8] = C[y]
    M = pow_mat([[1 if i == j else 0 for j in range(9)] for i in range(9)], M, n)
    X = mat_mul(M, [1, 0, 0, 0, 0, 0, 0, 0, 0])
    return X[-2]

for _ in range(int(input())):
    print(main())