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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
#include <iostream>

using namespace std;
typedef long long ll;

const ll nine_ans[][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 f(ll n) {
    while(n >= 10) {
        ll p = 1;
        while(n) {
            p *= n%10;
            n /= 10;
        }
        n = p;
    }
    return n;
}

int D[19];

int digits(ll n) {
    int l = 0;
    while(n) {
        D[++l] = n%10;
        n /= 10;
    }
    return l;
}

ll A[1009], ans[1009][10], pwr[10][19], binom[19][19];

ll how_many(int len, int cnt1, int cnt2, int cnt3, int cnt4, int cnt5, int cnt6, int cnt7, int cnt8, int cnt9, int s) {
    if(s == 0 || s > len) return 0;
    if(s < len) {
        return binom[s][cnt1]*
            binom[s-cnt1][cnt2]*
            binom[s-cnt1-cnt2][cnt3]*
            binom[s-cnt1-cnt2-cnt3][cnt4]*
            binom[s-cnt1-cnt2-cnt3-cnt4][cnt5]*
            binom[s-cnt1-cnt2-cnt3-cnt4-cnt5][cnt6]*
            binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6][cnt7]*
            binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6-cnt7][cnt8];
    }
    ll res = 0;
    bool ok = true;
    for(int pref = len; pref >= 1; --pref) {
        if(cnt1 && 1 < D[pref]) {
            res += binom[s-1][cnt1-1]*
                binom[s-cnt1][cnt2]*
                binom[s-cnt1-cnt2][cnt3]*
                binom[s-cnt1-cnt2-cnt3][cnt4]*
                binom[s-cnt1-cnt2-cnt3-cnt4][cnt5]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5][cnt6]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6][cnt7]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6-cnt7][cnt8];
        }
        if(cnt2 && 2 < D[pref]) {
            res += binom[s-1][cnt1]*
                binom[s-cnt1-1][cnt2-1]*
                binom[s-cnt1-cnt2][cnt3]*
                binom[s-cnt1-cnt2-cnt3][cnt4]*
                binom[s-cnt1-cnt2-cnt3-cnt4][cnt5]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5][cnt6]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6][cnt7]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6-cnt7][cnt8];
        }
        if(cnt3 && 3 < D[pref]) {
            res += binom[s-1][cnt1]*
                binom[s-cnt1-1][cnt2]*
                binom[s-cnt1-cnt2-1][cnt3-1]*
                binom[s-cnt1-cnt2-cnt3][cnt4]*
                binom[s-cnt1-cnt2-cnt3-cnt4][cnt5]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5][cnt6]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6][cnt7]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6-cnt7][cnt8];
        }
        if(cnt4 && 4 < D[pref]) {
            res += binom[s-1][cnt1]*
                binom[s-cnt1-1][cnt2]*
                binom[s-cnt1-cnt2-1][cnt3]*
                binom[s-cnt1-cnt2-cnt3-1][cnt4-1]*
                binom[s-cnt1-cnt2-cnt3-cnt4][cnt5]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5][cnt6]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6][cnt7]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6-cnt7][cnt8];
        }
        if(cnt5 && 5 < D[pref]) {
            res += binom[s-1][cnt1]*
                binom[s-cnt1-1][cnt2]*
                binom[s-cnt1-cnt2-1][cnt3]*
                binom[s-cnt1-cnt2-cnt3-1][cnt4]*
                binom[s-cnt1-cnt2-cnt3-cnt4-1][cnt5-1]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5][cnt6]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6][cnt7]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6-cnt7][cnt8];
        }
        if(cnt6 && 6 < D[pref]) {
            res += binom[s-1][cnt1]*
                binom[s-cnt1-1][cnt2]*
                binom[s-cnt1-cnt2-1][cnt3]*
                binom[s-cnt1-cnt2-cnt3-1][cnt4]*
                binom[s-cnt1-cnt2-cnt3-cnt4-1][cnt5]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-1][cnt6-1]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6][cnt7]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6-cnt7][cnt8];
        }
        if(cnt7 && 7 < D[pref]) {
            res += binom[s-1][cnt1]*
                binom[s-cnt1-1][cnt2]*
                binom[s-cnt1-cnt2-1][cnt3]*
                binom[s-cnt1-cnt2-cnt3-1][cnt4]*
                binom[s-cnt1-cnt2-cnt3-cnt4-1][cnt5]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-1][cnt6]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6-1][cnt7-1]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6-cnt7][cnt8];
        }
        if(cnt8 && 8 < D[pref]) {
            res += binom[s-1][cnt1]*
                binom[s-cnt1-1][cnt2]*
                binom[s-cnt1-cnt2-1][cnt3]*
                binom[s-cnt1-cnt2-cnt3-1][cnt4]*
                binom[s-cnt1-cnt2-cnt3-cnt4-1][cnt5]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-1][cnt6]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6-1][cnt7]*
                binom[s-cnt1-cnt2-cnt3-cnt4-cnt5-cnt6-cnt7-1][cnt8-1];
        }
        if(D[pref] == 0) {
            ok = false;
            break;
        }
        else if(D[pref] == 1) {
            if(cnt1) cnt1--;
            else {
                ok = false;
                break;
            }
        }
        else if(D[pref] == 2) {
            if(cnt2) cnt2--;
            else {
                ok = false;
                break;
            }
        }
        else if(D[pref] == 3) {
            if(cnt3) cnt3--;
            else {
                ok = false;
                break;
            }
        }
        else if(D[pref] == 4) {
            if(cnt4) cnt4--;
            else {
                ok = false;
                break;
            }
        }
        else if(D[pref] == 5) {
            if(cnt5) cnt5--;
            else {
                ok = false;
                break;
            }
        }
        else if(D[pref] == 6) {
            if(cnt6) cnt6--;
            else {
                ok = false;
                break;
            }
        }
        else if(D[pref] == 7) {
            if(cnt7) cnt7--;
            else {
                ok = false;
                break;
            }
        }
        else if(D[pref] == 8) {
            if(cnt8) cnt8--;
            else {
                ok = false;
                break;
            }
        }
        else if(D[pref] == 9) {
            if(cnt9) cnt9--;
            else {
                ok = false;
                break;
            }
        }
        s--;
    }
    if(ok) res++;
    return res;
}

int T[20][1009];
int T_cnt[20];

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t; cin >> t;
    for(int i = 1; i <= t; ++i) {
        cin >> A[i];
        int l = digits(A[i]);
        T[l][++T_cnt[l]] = i;
    }
    for(ll a = 1; a <= 9; ++a) {
        pwr[a][0] = 1;
        for(int b = 1; b <= 18; ++b) {
            pwr[a][b] = pwr[a][b-1]*a;
        }
    }
    for(int i = 0; i <= 18; ++i) {
        binom[i][0] = 1;
        for(int j = 1; j <= i; ++j) {
            binom[i][j] = binom[i-1][j-1]+binom[i-1][j];
        }
    }
    //int res = 0;
    for(int cnt1 = 0; cnt1 <= 18; ++cnt1) {
        for(int cnt2 = 0; cnt1+cnt2 <= 18; ++cnt2) {
            for(int cnt3 = 0; cnt1+cnt2+cnt3 <= 18; ++cnt3) {
                for(int cnt4 = 0; cnt1+cnt2+cnt3+cnt4 <= 18; ++cnt4) {
                    for(int cnt6 = 0; cnt1+cnt2+cnt3+cnt4+cnt6 <= 18; ++cnt6) {
                        for(int cnt7 = 0; cnt1+cnt2+cnt3+cnt4+cnt6+cnt7 <= 18; ++cnt7) {
                            for(int cnt8 = 0; cnt1+cnt2+cnt3+cnt4+cnt6+cnt7+cnt8 <= 18; ++cnt8) {
                                for(int cnt9 = 0; cnt1+cnt2+cnt3+cnt4+cnt6+cnt7+cnt8+cnt9 <= 18; ++cnt9) {
                                    int limit5 = min(18-(cnt1+cnt2+cnt3+cnt4+cnt6+cnt7+cnt8+cnt9),
                                    (cnt2+cnt4+cnt6+cnt8 == 0) ? 18 : 0);
                                    for(int cnt5 = 0; cnt5 <= limit5; ++cnt5) {
                                        //res++;
                                        //cout << cnt1 << " " << cnt2 << " " << cnt3 << " " << cnt4 << " " << cnt5 << " " << cnt6 << " " << cnt7 << " " << cnt8 << " " << cnt9 << "\n";
                                        int s = cnt1+cnt2+cnt3+cnt4+cnt5+cnt6+cnt7+cnt8+cnt9;
                                        ll prod = pwr[1][cnt1]*pwr[2][cnt2]*pwr[3][cnt3]*pwr[4][cnt4]*pwr[5][cnt5]*pwr[6][cnt6]*pwr[7][cnt7]*pwr[8][cnt8]*pwr[9][cnt9];
                                        int d = f(prod);
                                        if(d == 0) continue;
                                        for(int x = 1; x <= T_cnt[s]; ++x) {
                                            int index = T[s][x];
                                            int l = digits(A[index]);
                                            ll y = how_many(l, cnt1, cnt2, cnt3, cnt4, cnt5, cnt6, cnt7, cnt8, cnt9, s);
                                            ans[index][d] += y;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    for(int x = 1; x <= t; ++x) {
        int l = digits(A[x]);
        for(int d = 1; d <= 9; ++d) {
            ans[x][d] += nine_ans[l-1][d];
        }
        ll s = 0;
        for(int d = 1; d <= 9; ++d) {
            s += ans[x][d];
        }
        ans[x][0] = A[x]-s;
        for(int d = 0; d <= 9; ++d) {
            cout << ans[x][d] << " ";
        }
        cout << "\n";
    }

    return 0;
}