#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define int long long
mt19937_64 rnd(time(0));
int s[1000];
int n;
int check() {
    string str;
    str.resize(n);
    set<string> S;
    for(int i = 1;i <= n;i++) {
        str[i - 1] = s[i] + '0';
    }
    string tmp;
    tmp.resize(n);
    for(int i = 0;i < n;i++) {
        for(int j = i;j < n;j++) {
            for(int k = 0;k < n;k++) tmp[k] = str[k];
            for(int k = i;k <= j;k++) {
                if(str[i + j - k] == '6') tmp[k] = '9';
                if(str[i + j - k] == '9') tmp[k] = '6';
                if(str[i + j - k] == '0') tmp[k] = '0';
                if(str[i + j - k] == '8') tmp[k] = '8';
            }
//            cout << tmp << endl;
            S.insert(tmp);
        }
    }
    return S.size();
}

void solve() {
//    string s; cin >> s;
//    int n = (int)s.size();
//    s = ' ' + s;
    cin >> n;
    vector<int> base{0, 6, 8, 9};
    for(int i = 1;i <= n;i++) {
        s[i] = base[rnd() % 4];
    }
    bool fg = true;
    for(int i = 1;i <= n;i++) {
        if(s[i] == 0 || s[i] == 8) fg = false;
    }
    vector<int> dp(n + 1);
    vector<vector<int> > pre(4, vector<int> (n + 1));
    for(int i = 1;i <= n;i++) {
        pre[0][i] = pre[0][i - 1];
        pre[1][i] = pre[1][i - 1];
        pre[2][i] = pre[2][i - 1];
        pre[3][i] = pre[3][i - 1];
        if(s[i] == 0) pre[0][i] = pre[0][i - 1] + 1;
        if(s[i] == 6) pre[1][i] = pre[1][i - 1] + 1;
        if(s[i] == 8) pre[2][i] = pre[2][i - 1] + 1;
        if(s[i] == 9) pre[3][i] = pre[3][i - 1] + 1;
    }
    for(int i = 1; i <= n;i++) {
        dp[i] = dp[i - 1];
        if(s[i] == 0) dp[i] += i - 1 - pre[0][i - 1];
        if(s[i] == 8) dp[i] += i - 1 - pre[2][i - 1];
        if(s[i] == 6) dp[i] += i - pre[3][i - 1];
        if(s[i] == 9) dp[i] += i - pre[1][i - 1];
    }
    if(!fg) dp[n]++;
    if(check() != dp[n]) {
        cout << "WA" << endl;
        cout << check() << ' ' << dp[n] << endl;
        for(int j = 1;j <= n;j++) cout << s[j] <<  " \n"[j == n];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}