MOD = 998244353


def power(A, e):
    result = [[1 if i == j else 0 for j in range(len(A))] for i in range(len(A))]

    while e:
        if e % 2:
            result = multiply(result, A)
        A = multiply(A, A)
        e //= 2

    return result


def multiply(A, B):
    return [[sum(x * y % MOD for x, y in zip(A_row, B_col)) % MOD for B_col in zip(*B)] for A_row in A]


def multiply_vector(M, v):
    return [sum(M[i][j] * v[j] % MOD for j in range(len(v))) % MOD for i in range(len(M))]


X = [
    [1, 1, 1, 1, 0, 0, 0],  # 1
    [1, 1, 1, 1, 0, 0, 0],  # -1 ok
    [0, 0, 1, 1, 1, 1, 0],  # 2
    [0, 0, 1, 1, 1, 1, 0],  # -2
    [1, 0, 0, 0, 1, 1, 1],  # 4
    [1, 0, 0, 0, 1, 1, 1],  # -4
    [1, 0, 0, 0, 0, 0, 1],  # -1 ng
]

Y = [
    [1, 1],
    [1, 1],
]


def solve():
    N = int(input())
    ans = multiply_vector(power(X, N), [1])[0]
    ans -= multiply_vector(power(Y, N), [1])[0]
    print(ans % MOD)


if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        solve()