#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// Base 10^18 極限壓縮
const uint64_t BASE = 1000000000000000000ULL;
const uint64_t CARRY_BASE[5] = {0, BASE, 2 * BASE, 3 * BASE, 4 * BASE};

int main() {
    // 優化 I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    if (!(cin >> T)) return 0;
    
    // 1. 離線讀取所有查詢，找出最大的 N
    vector<int> queries(T);
    int max_n = 0;
    for (int i = 0; i < T; i++) {
        cin >> queries[i];
        if (queries[i] > max_n) {
            max_n = queries[i];
        }
    }
    
    // 2. 準備全域快取 (Global Cache)
    string D = "5"; 
    D.reserve(max_n + 1);
    
    vector<uint64_t> Q;
    Q.reserve(max_n / 18 + 2);
    Q.push_back(1);
    
    vector<uint64_t> P;
    P.reserve(max_n / 18 + 2);
    P.push_back(2);
    
    int odds[5] = {1, 3, 5, 7, 9};
    
    // 3. 一次性建表直到 max_n
    int current_k = 1;
    while (current_k < max_n) {
        current_k++;
        
        uint32_t rem_Q = Q[0] % 5;
        uint32_t rem_P = P[0] % 5;
        
        int chosen_d = 1;
        for (int i = 0; i < 5; i++) {
            if ((odds[i] * rem_P + rem_Q) % 5 == 0) {
                chosen_d = odds[i];
                break;
            }
        }
        D.push_back(chosen_d + '0');
        
        while (Q.size() < P.size()) {
            Q.push_back(0);
        }
        
        // 更新 Q = (Q + chosen_d * P) / 5
        uint64_t carry_div = 0;
        int p_size = P.size();
        for (int i = (int)Q.size() - 1; i >= 0; i--) {
            uint64_t val = Q[i] + CARRY_BASE[carry_div];
            if (i < p_size) {
                val += chosen_d * P[i];
            }
            Q[i] = val / 5;
            carry_div = val % 5;
        }
        
        while (Q.size() > 1 && Q.back() == 0) {
            Q.pop_back();
        }
        
        // 更新 P = P * 2
        uint64_t carry_mul = 0;
        for (int i = 0; i < p_size; i++) {
            uint64_t val = P[i] * 2 + carry_mul;
            if (val >= BASE) {
                P[i] = val - BASE;
                carry_mul = 1;
            } else {
                P[i] = val;
                carry_mul = 0;
            }
        }
        if (carry_mul > 0) {
            P.push_back(carry_mul);
        }
    }
    
    // 4. O(1) 擷取並回應所有查詢
    for (int i = 0; i < T; i++) {
        int n = queries[i];
        string ans = D.substr(0, n);
        reverse(ans.begin(), ans.end());
        cout << ans << "\n";
    }
    
    return 0;
}