def matmul(a, b): n = len(a) c = [[0] * n for _ in range(n)] for i in range(n): for j in range(n): for k in range(n): c[i][j] += a[i][k] * b[k][j] c[i][j] %= 998244353 return c def matpow(A, k): res = [[int(i == j) for j in range(len(A))] for i in range(len(A))] p = A while k: if k & 1: res = matmul(res, p) p = matmul(p, p) k >>= 1 return res T = int(input()) for _ in range(T): n = int(input()) state = [1, -1, 2, -2, 4, -4, -8, 1, -1] select = [1, -1, 2, -2] sz = len(state) mat = [[0] * sz for _ in range(sz)] for i in range(sz): for y in select: x = state[i] z = x * y if z == 8: j = 0 elif z not in state: continue elif 7 <= i and z == 1: j = 7 elif 7 <= i and z == -1: j = 8 else: j = state.index(z) mat[i][j] += 1 """ for line in mat: print(line) print("-" * 30) """ res = matpow(mat, n) print(res[7][0])