#include <iostream>
#include <vector>
using namespace std;

int main() {
    int Q;
    cin >> Q;

    while (Q--) {
        int n;
        cin >> n;
        cout << (n % 2 ? 4 : 998244349) << '\n';
    }
}