# ZeroJudge - g556: 白色世界(困難版)
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=g556
###### tags: `ZeroJudge` `動態規劃（Dynamic Programming）` `數學` `數論` `快速冪`

#include <iostream>
using namespace std;
#define MOD 998244353

int matrices[64][2][2] = { { { 0, 1 }, { 1, 1 } } }, buffer[2][2];

static const auto Initialize = [] {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	for (int i = 1; i < 64; ++i)
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 2; ++k)
				for (int l = 0; l < 2; ++l)
					matrices[i][j][k] = (matrices[i][j][k] + (long long)matrices[i - 1][j][l] * matrices[i - 1][l][k]) % MOD;
	return nullptr;
}();

int FastPower(long long power) {
	int answer[2][2] = { { 1, 0 }, { 0, 1 } }, nowPower = 0;
	while (power) {
		if (power & 1) {
			for (int i = 0; i < 2; ++i)
				for (int j = 0; j < 2; ++j) {
					buffer[i][j] = 0;
					for (int k = 0; k < 2; ++k)
						buffer[i][j] = (buffer[i][j] + (long long)answer[i][k] * matrices[nowPower][k][j]) % MOD;
				}
			for (int i = 0; i < 2; ++i)
				for (int j = 0; j < 2; ++j)
					answer[i][j] = buffer[i][j];
		}
		++nowPower; power >>= 1;
	}
	return ((long long)answer[0][0] + (answer[0][1] << 1) + MOD - 1) % MOD;
}

int main() {
	int times;
	long long nth;
	cin >> times;
	while (times--) {
		cin >> nth;
		cout << FastPower(nth) << '\n';
	}
}