function Main(input) {
	const r = [1n, 1n];
	const e = [1n, 3n];
	const lines = input.split('\n').map(x => x.trim()).filter(Boolean);
	const mod = 998244353n;
	lines.slice(1).forEach(line => {
		const n = +line - 1;
		while (r.length <= n) {
			r.push((r.at(-1) + r.at(-2)) % mod);
			e.push((e.at(-1) + e.at(-2)) % mod);
		}
		const result = (5n * r[n] * r[n] - e[n] * e[n]);
		console.log(((result % mod) + mod) % mod);
	});
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));