# ZeroJudge - h399: 蛋糕店促銷（簡易版）以及 h400: 蛋糕店促銷（困難版）
### 題目連結：
https://zerojudge.tw/ShowProblem?problemid=h399
https://zerojudge.tw/ShowProblem?problemid=h400
###### tags: `ZeroJudge` `數學` `數論` `貪心演算法（Greedy Algorithm）` `快速冪`

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

static const auto Initialize = [] {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	return nullptr;
}();

int FastPower(int number, int power) {
	int answer = 1, buffer = number;
	while (power) {
		if (power & 1)
			answer = ((long long)answer * buffer) % MOD;
		buffer = ((long long)buffer * buffer) % MOD;
		power >>= 1;
	}
	return answer;
}

int main() {
	int times, partition, twos, threes;
	long long number;
	cin >> times;
	while (times--) {
		cin >> number;
		if (number <= 4) {
			cout << number << '\n';
			continue;
		}
		switch (number % 3) {
		case 0:
			cout << FastPower(3, number / 3) << '\n';
			break;
		case 1:
			cout << ((long long)FastPower(3, number / 3 - 1) << 2) % MOD << '\n';
			break;
		default:
			cout << ((unsigned)FastPower(3, number / 3) << 1) % MOD << '\n';
		}
	}
}