// Author: lzm0107

#include <bits/stdc++.h>

using namespace std;

constexpr int kMod = 998'244'353, kInf32 = 0x3f3f3f3f;

inline constexpr int Mod(int x) {
    return x >= kMod ? x - kMod : x;
}

constexpr int kMaxN = 200'000;

int pw10[kMaxN + 10];

int n, p[kMaxN + 10], q[kMaxN + 10], prefix_hash[kMaxN + 10];
int ans[kMaxN + 10];

int sparse_table[2][__lg(kMaxN) + 2][kMaxN + 10];

struct Node {
    bool complete;
    int hash_val, len;
    int frontmin, min_inversion;
    Node operator+(Node rhs) const {
        return {complete || rhs.complete,
                (int)(((long long)hash_val * pw10[rhs.len] + rhs.hash_val) % kMod),
                len + rhs.len, min(frontmin, rhs.frontmin),
                min(min_inversion, rhs.min_inversion)};
    }
};

Node d[(4 << __lg(kMaxN + 1)) + 10];
int pn;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    pw10[0] = 1;
    for (int i = 1; i <= kMaxN; i++) {
        pw10[i] = 10ll * pw10[i - 1] % kMod;
    }

    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> p[i];
            prefix_hash[i] = (10ll * prefix_hash[i - 1] + p[i]) % kMod;
            q[p[i]] = i;
            sparse_table[0][0][i] = sparse_table[1][0][i] = p[i];
        }
        for (int i = 1; 1 << i <= n; i++) {
            for (int j = 1; j + (1 << i) - 1 <= n; j++) {
                sparse_table[0][i][j] = min(sparse_table[0][i - 1][j], sparse_table[0][i - 1][j + (1 << i - 1)]);
                sparse_table[1][i][j] = max(sparse_table[1][i - 1][j], sparse_table[1][i - 1][j + (1 << i - 1)]);
            }
        }
        auto get_range_hash = [&](int l, int r) -> int {
            return Mod(prefix_hash[r] + kMod - (long long)prefix_hash[l - 1] * pw10[r - l + 1] % kMod);
        };
        auto get_range_min = [&](int l, int r) -> int {
            int tmp = 31 ^ __builtin_clz(r - l + 1);
            return min(sparse_table[0][tmp][l], sparse_table[0][tmp][r - (1 << tmp) + 1]);
        };
        auto get_range_max = [&](int l, int r) -> int {
            int tmp = 31 ^ __builtin_clz(r - l + 1);
            return max(sparse_table[1][tmp][l], sparse_table[1][tmp][r - (1 << tmp) + 1]);
        };

        set<int> segment_start;
        auto get_rep = [&](int x) -> int {
            return *segment_start.rbegin() == x ? n : *segment_start.upper_bound(x) - 1;
        };

        pn = 2 << (31 ^ __builtin_clz(n + 1));
        for (int i = 1; i < pn * 2; i++) {
            d[i] = {false, 0, 0, kInf32, kInf32};
        }

        auto find_greater = [&](int x) -> int {
            x += pn;
            for (; x > 0; x >>= 1) {
                if ((x & 1 ^ 1) && d[x ^ 1].complete) {
                    x ^= 1;
                    break;
                }
            }
            if (x == 0) {
                return -1;
            }
            while (x < pn) {
                x <<= 1;
                if (!d[x].complete) {
                    x ^= 1;
                }
            }
            return x - pn;
        };
        auto find_less = [&](int x) -> int {
            x += pn;
            for (; x > 0; x >>= 1) {
                if ((x & 1) && d[x ^ 1].complete) {
                    x ^= 1;
                    break;
                }
            }
            if (x == 0) {
                return -1;
            }
            while (x < pn) {
                x <<= 1;
                if (d[x ^ 1].complete) {
                    x ^= 1;
                }
            }
            return x - pn;
        };
        auto query = [&](int l, int r) -> int {
            int result = 0;
            for (l += pn - 1, r += pn + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
                if (l & 1 ^ 1) {
                    result += d[l ^ 1].len;
                }
                if (r & 1) {
                    result += d[r ^ 1].len;
                }
            }
            return result;
        };

        auto update = [&](int x) -> void {
            if (!segment_start.count(x)) {
                d[p[x] + pn] = {false, 0, 0, kInf32, kInf32};
            } else {
                int rep = get_rep(x), tmp = get_range_min(x, rep), nex = find_greater(p[x]);
                d[p[x] + pn] = {true, get_range_hash(x, rep), rep - x + 1, (tmp == p[x] ? kInf32 : tmp), (nex != -1 && get_range_max(x, rep) > nex ? p[x] : kInf32)};
            }
            for (int i = p[x] + pn >> 1; i > 0; i >>= 1) {
                d[i] = d[i << 1] + d[i << 1 | 1];
            }
        };

        segment_start.insert(1);
        update(1);

        auto flip_cut_state = [&](int x) -> void {
            if (segment_start.count(x)) {
                segment_start.erase(x);
            } else {
                segment_start.insert(x);
            }
            update(x);
            if (segment_start.lower_bound(x) != segment_start.begin()) {
                update(*prev(segment_start.lower_bound(x)));
            }
            int prv = find_less(p[x]);
            if (prv != -1) {
                update(q[prv]);
            }
        };

        int cur_prefix = 0;
        while ((int)segment_start.size() <= n) {
            ans[segment_start.size()] = d[1].hash_val;
            if (cur_prefix == n) {
                for (int i = (int)segment_start.size() + 1; i <= n; i++) {
                    ans[i] = ans[i - 1];
                }
                break;
            }

            bool condition0 = (cur_prefix > 0 && q[cur_prefix] != n && p[q[cur_prefix] + 1] > cur_prefix + 1);
            bool condition1 = (q[cur_prefix + 1] != 1 && p[q[cur_prefix + 1] - 1] > cur_prefix + 1);
            if (condition0 && condition1) {
                int val0, effect0;
                int val1, effect1;
                if (d[1].frontmin == kInf32) {
                    val0 = effect0 = kInf32;
                } else {
                    val0 = d[1].frontmin;
                    int tmp = find_greater(val0);
                    effect0 = query(1, tmp - 1) + 1;
                }
                if (d[1].min_inversion == kInf32) {
                    val1 = effect1 = kInf32;
                } else {
                    val1 = find_greater(d[1].min_inversion);
                    int pos = q[d[1].min_inversion];
                    int l = pos, r = n;
                    while (l + 1 < r) {
                        int mid = l + r >> 1;
                        if (get_range_max(pos, mid) > val1) {
                            r = mid;
                        } else {
                            l = mid;
                        }
                    }
                    effect1 = query(1, p[pos] - 1) + 1 + r - pos;
                    val1 = p[r];
                }

                if (effect0 == kInf32 && effect1 == kInf32) {
                    ans[segment_start.size() + 1] = d[1].hash_val;
                } else {
                    if (effect0 < effect1) {
                        flip_cut_state(q[val0]);
                    } else {
                        flip_cut_state(q[val1]);
                    }
                    ans[segment_start.size()] = d[1].hash_val;
                    if (effect0 < effect1) {
                        flip_cut_state(q[val0]);
                    } else {
                        flip_cut_state(q[val1]);
                    }
                }
            }
            if (condition0) {
                flip_cut_state(q[cur_prefix] + 1);
            }
            if (condition1) {
                flip_cut_state(q[cur_prefix + 1]);
            }
            ++cur_prefix;
        }
        for (int i = 1; i <= n; i++) {
            cout << ans[i] << ' ';
        }
        cout << '\n';
    }
}