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
#include <algorithm>
#include <bits/stdc++.h>
#include <numeric>
#include <unordered_map>
using namespace std;

#define all(a) begin(a), end(a)
using ll = long long;

constexpr int K = 19;
ll pw[K];

// struct FastMap {
//     vector<pair<ll, ll>> data;
//     FastMap(vector<ll> keys = {}) : data(keys.size()) {
//         // sort(all(keys));
//         for (int i = 0; i < keys.size(); i++)
//             data[i] = {keys[i], 0};
//     }
//
//     ll &get(ll key) {
//         auto it = lower_bound(all(data), pair<ll, ll>{key, 0});
//         assert(it->first == key);
//         return it->second;
//     }
//
//     void optimize_immutable() {
//         data.erase(remove_if(all(data), [](pair<ll, ll> p) { return p.second == 0; }), end(data));
//     }
// };

ll run(ll n) {
    while (n >= 10) {
        ll t = 1;
        while (n) {
            t *= n % 10;
            n /= 10;
        }
        n = t;
    }

    return n;
}

using R = array<ll, 10>;
R add(R x, R const &y) {
    for (int i = 0; i < 10; i++)
        x[i] += y[i];
    return x;
}

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

map<ll, R> pre_ans[K];
R get(ll n) {
    ll h = 0;
    while (h < K && n >= pw[h])
        h++;
    h--;

    R res = pre9[h];

    ll prod = 1;
    bool first = true;
    for (; h >= 0; h--) {
        ll d = n / pw[h] % 10;
        for (int i = first ? 1 : 0; i < d; i++)
            res = add(res, pre_ans[h][prod * i]);

        prod *= d;
        first = false;
    }

    res[run(n)]++;
    return res;
}

vector<ll> add_digit(vector<ll> const &a) {
    int n = a.size();
    vector<ll> result(10 * n);
    for (int d = 0; d < 10; d++)
        for (int i = 0; i < a.size(); i++)
            result[d * n + i] = d * a[i];
    sort(all(result));
    result.erase(unique(all(result)), end(result));
    return result;
}

void init() {
    pw[0] = 1;
    for (int i = 1; i < K; i++)
        pw[i] = 10 * pw[i - 1];

    vector<ll> keys[K];
    keys[0] = {1};
    for (int i = 1; i < K; ++i)
        keys[i] = add_digit(keys[i - 1]);

    for (auto i : keys[K - 1]) {
        R r;
        fill(all(r), 0);
        r[run(i)] = 1;
        pre_ans[0][i] = r;
    }

    for (int h = 1; h < K; h++) {
        for (auto i : keys[K - 1 - h]) {
            R r;
            fill(all(r), 0);

            for (int d = 0; d < 10; d++)
                r = add(r, pre_ans[h - 1][i * d]);

            pre_ans[h][i] = r;
        }
    }
}

void solve() {
    ll n;
    cin >> n;

    auto result = get(n);
    assert(accumulate(all(result), 0ll) == n);

    for (auto i : result)
        cout << i << " ";
    cout << "\n";
}

int main() {
    init();

    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int tests = 1;
    cin >> tests;

    while (tests--)
        solve();
}