from functools import cache import sys sys.setrecursionlimit(10000000) @cache def fibonacci(N: int) -> int: if N in (1, 2): return 1 return fibonacci(N - 2) + fibonacci(N - 1) @cache def fibonacci_mod(N: int, mod: int) -> int: if N in (1, 2): return 1 return (fibonacci_mod(N - 2, mod) + fibonacci_mod(N - 1, mod)) % mod @cache def nacci_e(N: int, mod: int) -> int: if N == 1: return 1 if N == 2: return 3 return (nacci_e(N - 1, mod) + nacci_e(N - 2, mod)) % mod def calc_width_diff(N: int) -> int: MOD = 998244353 return ((5 * fibonacci_mod(N, MOD) ** 2) % MOD - nacci_e(N, MOD) ** 2) % MOD def main(): for _ in range(int(input())): N = int(input()) print(calc_width_diff(N)) if __name__ == "__main__": main()