1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstring>

using namespace std;

typedef long long ll;


ll getDigMull(ll val) {
    ll res = val % 10;
    val /= 10;
    while (res > 0 && val > 0) {
        res *= val % 10;
        val /= 10;
    }
    return res;
}
int getRes(ll val) {
    while (val >= 10) {
        val = getDigMull(val);
    }
    return val;
}

ll fact[20];
ll p10[20];

int cnt[10];
int dig[20];

int init(ll val) {
    for (int i = 0; i < 20; i++) {
        dig[i] = val % 10;
        val /= 10;
    }
    int p = 19;
    while ((p >= 0) && (dig[p] == 0)) p--;
    return p + 1;
}


ll getAll(int sum) {
    ll res = fact[sum];
    for (int i = 0; i < 10; i++) 
        res /= fact[cnt[i]];
    return res;
}

ll getCnt(int p, bool zero) {
    if (p < 0)
        return 1;
   ll res = 0;
   for (int i = zero ? 0 : 1; i < dig[p]; i++) {
        if (cnt[i] > 0 ) {
            cnt[i]--;
            res += getAll(p);
            cnt[i]++;    
        }
    }
    if (cnt[dig[p]] > 0) {
        cnt[dig[p]]--;
        res += getCnt(p - 1, true);
        cnt[dig[p]]++;
    }
    return res;
}

ll prec[19][10] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 1},
{24, 2, 9, 3, 10, 7, 14, 3, 23, 4},
{476, 3, 77, 6, 65, 40, 155, 6, 161, 10},
{6739, 4, 543, 10, 279, 172, 1172, 10, 1050, 20},
{82401, 5, 3213, 15, 894, 607, 6843, 15, 5971, 35},
{902608, 6, 16673, 21, 2345, 2073, 43538, 21, 32658, 56},
{9394517, 7, 86093, 28, 6174, 7414, 318457, 28, 187197, 84},
{96122290, 8, 503815, 36, 66354, 26070, 2223803, 36, 1057467, 120},
{975700392, 9, 3529057, 45, 1005399, 84099, 14185700, 45, 5495088, 165},
{9854082822, 10, 25402097, 55, 9737884, 243529, 84670477, 55, 25862850, 220},
{99180099587, 11, 162303510, 66, 66699415, 636130, 477808607, 66, 112452321, 286},
{995679223590, 12, 884504882, 78, 356586629, 1518166, 2577052118, 78, 501114082, 364},
{9977627937023, 13, 4156234265, 91, 1585685916, 3354325, 13759255632, 91, 2867532188, 455},
{99879659224379, 14, 17270407962, 105, 6342292785, 6940831, 75251167843, 105, 21469965415, 560},
{999321444658475, 15, 65375131342, 120, 30560724590, 13579716, 418157757456, 120, 164448147485, 680},
{9996118748668338, 16, 232901619970, 136, 264486626166, 25318372, 2267313716636, 136, 1116524049413, 816},
{99978099721506172, 17, 807191392546, 153, 2926013859615, 45270813, 11616142299625, 153, 6550885669936, 969},
{999879067589400315, 18, 2795912956450, 171, 28611339267816, 78039555, 55909713312571, 171, 33615367021792, 1140},
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    fact[0] = 1;
    p10[0] = 1;
    for (int i = 1; i < 20; i++) {
        fact[i] = fact[i - 1] * i;
        p10[i] = p10[i - 1] * 10;
    }
    int t;
    cin >> t;
    while (t--) {
        ll n;
        cin >> n; 

        int dlen = init(n);
        ll ans[10] = {};        
        memmove(ans, prec[dlen - 1], sizeof(ans));
//        cout << "dlen = " << dlen << "\n";
        ll p9 = 1;
        for (int i9 = 0; i9 <= dlen; i9++) {
            int r9 = dlen - i9;
            cnt[9] = i9;
            ll p8 = p9;
            for (int i8 = 0; i8 <= r9; i8++) {
                int r8 = r9 - i8;
                cnt[8] = i8;
                ll p7 = p8;
                for (int i7 = 0; i7 <= r8; i7++) {
                    int r7 = r8 - i7;
                    cnt[7] = i7;
                    ll p6 = p7;
                    for (int i6 = 0; i6 <= r7; i6++) {
                        int r6 = r7 - i6;
                        cnt[6] = i6;
                        ll p5 = p6;
                        for (int i5 = 0; i5 <= r6; i5++) {
                            int r5 = r6 - i5;
                            cnt[5] = i5;
                            ll p4 = p5;
                            for (int i4 = 0; i4 <= r5; i4++) {
                                int r4 = r5 - i4;
                                cnt[4] = i4;
                                ll p3 = p4;
                                for (int i3 = 0; i3 <= r4; i3++) {
                                    int r3 = r4 - i3;
                                    cnt[3] = i3;
                                    ll p2 = p3;
                                    for (int i2 = 0; i2 <= r3; i2++) {
                                        int r2 = r3 - i2;
                                        cnt[2] = i2;
                                        ll res2 = getRes(p2);
                                        for (int i1 = 0; i1 <= r2; i1++) {
                                            int r1 = r2 - i1;
                                            cnt[1] = i1;
                                            cnt[0] = r1;
                                            ll res = r1 > 0 ? 0 : res2;
                                            ll vcnt = getCnt(dlen - 1, false);
                                            ans[res] += vcnt;
                                            //for (int i = 0; i < 10; i++) {
                                            //    cout << cnt[i] << " :"[i == 9];
                                            //}
                                            //cout << " res = " << res << " vcnt = " << vcnt << "\n"; 
                                        }
                                        p2 *= 2;
                                    }
                                    p3 *= 3;
                                }
                                p4 *= 4;
                            }
                            p5 *= 5;
                        }
                        p6 *= 6;
                    }
                    p7 *= 7;
                }
                p8 *= 8;
            }
            p9 *= 9;
        }


        for (int i = 0; i < 10; i++) {
            cout << ans[i] << ((i < 9) ? " " : "\n");
        }
    }
    return 0;
}