#include<iostream>
#include<string>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using mint = modint998244353;

vector<mint> mul(vector<mint>& a, vector<mint>& b) {
	vector<mint> res = { a[0] * b[0] + a[1] * b[2],a[0] * b[1] + a[1] * b[3],a[2] * b[0] + a[3] * b[2],a[2] * b[1] + a[3] * b[3] };
	return res;
}

vector<mint> power(long long n, vector<mint>& mut) {
	vector<mint> res = { 1,0,0,1 };
	if (n == 0)
		return res;
	auto pow = mul(mut, mut);
	res = power(n / 2, pow);
	if (n % 2)res = mul(res, mut);
	return res;
}

int main() {
	int q;
	cin >> q;
	vector<mint> mut = { 0,1,1,1 };
	for(int i=0; i<q; i++){
		int n;
		cin>>n;
		auto res = power(n - 1, mut);
		cout << (5 * (res[0] + res[1]) * (res[0] + res[1]) - (res[0] + 3 * res[1]) * (res[0] + 3 * res[1])).val() << "\n";
	}
}