#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
using ll = long long;

#include<set>
#include<atcoder/segtree>
#include<atcoder/modint>
#include<cassert>
using mint = atcoder::modint998244353;

using dat1 = pair<pair<mint,mint>,pair<int,int>>;
dat1 op1(dat1 a,dat1 b) {
    dat1 now;
    now.first.first = a.first.first * b.first.second + b.first.first;
    now.first.second = a.first.second * b.first.second;
    return now;
}

dat1 e1(){
    return make_pair(make_pair(0, 1), make_pair(-1, -1));
}

using dat2 = int;
dat2 op2(dat2 a,dat2 b) {
    return min(a,b);
}
dat2 e2() {
    return 1e9;
}

using dat3 = int;
dat3 op3(dat3 a,dat3 b){
    return max(a,b);
}
dat3 e3(){
    return -1;
}

int fuse = 0;
int f1(dat3 a) {
    return a < fuse;
}
void solve(){ 
    int n;
    cin>>n;
    vector<int> p(n);
    for(int i = 0;i<n;i++) cin>>p[i];
    for(int i = 0;i<n;i++) p[i]--;
    vector<int> idx(n);
    for(int i = 0;i<n;i++) {
        idx[p[i]] = i;
    }

    atcoder::segtree<dat1, op1, e1> seg1(n);
    // 数字の index
    set<int> use;
    // 場所の index
    set<int> cutuse;  

    atcoder::segtree<dat2, op2, e2> pmin(p);
    atcoder::segtree<dat3, op3, e3> pmax(p);
    atcoder::segtree<dat1, op1, e1> psum(n);
    atcoder::segtree<dat3, op3, e3> usemax(n);
    atcoder::segtree<dat2, op2, e2> usemin(n);
    for(int i = 0;i<n;i++) {
        psum.set(i, make_pair(make_pair(p[i] + 1, 10),make_pair(i, i)));
    }


    atcoder::segtree<dat2, op2, e2> can(n);
    atcoder::segtree<dat2, op2, e2> notuse(n);
    for(int i = 0;i<n;i++) notuse.set(i, i);
    vector<int> ok(n, 0);
    atcoder::segtree<dat3, op3, e3> conmax(n);
    atcoder::segtree<dat2, op2, e2> ausemin(n);

    vector<int> mcan(n);
    set<int> ook;
    int ng = 0;

    auto judge = [&](int i) {
        // cout<<"j1"<<endl;
        can.set(i, e2());
        auto itr = use.find(i);
        if(itr==use.begin()) return;
        itr--;
        int ni = *itr;
        int l = seg1.get(ni).second.first;
        int r = seg1.get(ni).second.second + 1;
        if(pmax.prod(l, r) > i) {
            while(r-l>1){
                int m = (r+l) / 2;
                if(pmax.prod(l, m) > i) r = m;
                else l = m;
            }
            mcan[i] = l;
            can.set(i, i);
        }

        ausemin.set(i, e2());
        l = seg1.get(i).second.first;
        r = seg1.get(i).second.second;
        int pp = pmin.prod(l, r + 1);
        if(pp<i) ausemin.set(i, pp);
    };

    auto add = [&](dat1 now,int i) {
        use.insert(i);
        notuse.set(i, e2());
        cutuse.insert(now.second.first);
        usemax.set(idx[i], idx[i]);
        usemin.set(i, i);
        ok[i] = 1;
        seg1.set(i, now);
        conmax.set(i, pmax.prod(now.second.first, now.second.second+1));

        can.set(i, e2());
        judge(i);
        auto itr = use.upper_bound(i);
        if(itr!=use.end()) {
            int ni = *itr;
            can.set(ni,e2());
            judge(ni);
        }
    };

    auto erase = [&](int i) {
        auto ee = seg1.get(i);
        use.erase(i);
        notuse.set(i, i);
        cutuse.erase(ee.second.first);
        ok[i] = 0;
        conmax.set(i, e3());
        seg1.set(i, e1());
        usemin.set(i, e2());
        usemax.set(idx[i], e3());

        can.set(i, e2());
        auto itr = use.upper_bound(i);
        if(itr!=use.end()) {
            int ni = *itr;
            can.set(ni, e2());
            judge(ni);
        }
    };

    for(int i = 0;i<n;i++){
        // if(p[i]==i) {
        //     dat1 now;
        //     now.first.first = p[i] + 1;
        //     now.first.second = 10;
        //     now.second.first = i;
        //     now.second.second = i;
        //     add(now, i);
        //     continue;
        // }

        int ni = p[i];
        dat1 now;
        now.first.first = 0;
        now.first.second = 1;
        now.second.first = i;
        now.second.second = n - 1;
        for(int j = i;j<n;j++){
            now.first.first *= 10;
            now.first.first += p[j] + 1;
            now.first.second *= 10;
        }
        add(now, ni);
        break;
    }

    vector<mint> ans(n+1);
    int last = 0;
    
    vector<pair<pair<int,int>,dat1>> rr;
    auto cut = [&](int i) {
        if(i==0) return;
        assert(i!=0);
        auto itr = cutuse.lower_bound(i);
        int r = n;
        if(itr!=cutuse.end()) r = *itr;
        assert(itr!=cutuse.begin());
        itr--;
        int l = *itr;

        int nl = p[l];
        dat1 nnl = seg1.get(nl);
        //rr.push_back(make_pair(make_pair(nl, 0), nnl));
        //erase(nl);
        
        dat1 newl = nnl;
        newl.second.second = i - 1;
        rr.push_back(make_pair(make_pair(nl, 1), seg1.get(nl)));
        newl.first = psum.prod(l, i).first;
        add(newl, nl);

        dat1 newi;
        newi.second.first = i;
        newi.second.second = r - 1;
        newi.first = psum.prod(i, r).first;
        rr.push_back(make_pair(make_pair(p[i], 1), seg1.get(p[i])));
        add(newi, p[i]);
    };
    ans[0] = seg1.all_prod().first.first;

    auto j2 = [&]() {
        while(true){
            if(ng==n) return;
            if(use.find(ng)!=use.end()){
                ng++;
                continue;
            }
            int ii = idx[ng];
            auto itr = cutuse.lower_bound(ng);
            itr--;

            int ni = *itr;
            ni = p[ni];
            if(ng<=ni){
                ng++;
                continue;
            }
            return;
        }
    };  

    for(int t = 1;t < n;) {
        mint tmp = 0;
        if(last==n){
            ans[t] = seg1.all_prod().first.first;
            t++;
            continue;
        }

        {
            int ni = idx[last];
            int nj = ni - 1;
            if(0<=nj && p[nj] == last - 1) {
                cut(ni);
            }
        }

        // assert(last!=n-1);
        int ni = last + 1;
        int need = 0;

        rr.clear();
        int pos = n;
        if(last-1>=0) pos = idx[last-1] + 1;

        if(pos!=n && cutuse.find(pos) == cutuse.end()) need++;
        if(cutuse.find(idx[last])==cutuse.end()) need++;
        if(need==0){
            last++;
            continue;
        }
        if(need==2) {
            //j2();
            int aa = ausemin.all_prod();
            aa = min(aa, n);
            auto itr = use.upper_bound(aa);
            int bb = can.all_prod();
            bool fn = false;
            int wc;
            //cout<<t<<" "<<aa<<" "<<bb<<endl;
            if(0 <= bb && bb < n) {
                if(itr!=use.end()){
                    int ma = *itr;
                        int mb = can.all_prod();
                        //cout<<t<<" "<<ma<<" "<<mb<<" "<<mcan[bb]<<endl;
                        if(ma>=mb) {
                            fn = true;
                            wc = p[mcan[bb]];
                            //cout<<wc<<endl;
                        }
                }else{
                    fn = true;
                    wc = p[mcan[bb]];
                }
            }else{
                wc = aa;
            }
            //cout<<fn<<endl;
            // if(itr==use.end()) {
            //     if(bb<n){
            //         cout<<n<<endl;
            //         for(int i = 0;i<n;i++) cout<<p[i]<<" ";
            //         cout<<endl;
            //         cout<<t<<endl;
            //         cout<<aa<<" "<<bb<<endl;
            //     }
            //     assert(bb>=n);
            // }

            if(fn) {
                //cout<<t<<" "<<wc<<endl;
                cut(idx[wc]);
                tmp = seg1.all_prod().first.first;
            }else{
                if(aa==n) aa--;
                //cout<<t<<" "<<aa<<endl;
                cut(idx[aa]);
                tmp = seg1.all_prod().first.first;
            }
            // cout<<fn<<" "<<wc<<" "<<aa<<endl;
            // cout<<t<<" "<<seg1.get(0).first.first.val()<<endl;
   
            reverse(rr.begin(),rr.end());
            for(auto e:rr){
                if(e.first.second==1) erase(e.first.first);
                else add(e.second, e.first.first);
            }
            
        }

        if(pos!=n && cutuse.find(pos) == cutuse.end()){
            cut(pos);
        }else{
            int ni = idx[last];
            assert(cutuse.find(ni)==cutuse.end());
            cut(ni);
        }
        
        if(need!=2) {
            ans[t] = seg1.all_prod().first.first;
        }else{
            ans[t] = tmp;
        }
        t++;
        continue;
    }

    for(int i = 0;i<n;i++){
        cout<<ans[i].val();
        if(i!=n-1) cout<<" ";
        else cout<<endl;
    }
}

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

    int t;
    cin>>t;
    while(t--){
        solve();
    }
}