给定两个数列递推式，直接递推求解即可，注意取模的彻底，只进行一次初始化即可。

参考代码：

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using u128 = unsigned __int128;

constexpr int N = 100010, mod = 998244353;

std::vector<i64> f(N), g(N);

void init(int n) {
	f[1] = 1;
	f[2] = 2;
	for (int i = 3; i < n; i++) {
		f[i] = (2 * f[i - 1] % mod + 3 * f[i - 2] % mod + i) % mod;
	}
	g[1] = 2;
	for (int i = 2; i < n; i++) {
		g[i] = (g[i - 1] % mod + f[i] % mod + (i64)i * i % mod) % mod;
	}
}

void solve() {
	int n;
	std::cin >> n;
	std::cout << g[n] % mod << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	init(N);

	int t; 
	std::cin >> t;
	while (t --) {
		solve();
	}

	return 0;
}