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
#include <bits/stdc++.h>
#define dbg(x) #x << " = " << x << " "
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
constexpr ll  MAX_LEN = 19, MAX_CYFRA = 9,
             MAX_GENERATORKI = 66063;

ll MAX_N;

// dp[g][l][c] = Ile liczb o l cyfrach (bez zer) tż. najbardziej znacząca cyfra jest <= c trafia w
// pierwszym ruchu do g-tej generatorki.
ll dp[MAX_GENERATORKI + 5][MAX_LEN + 5][MAX_CYFRA + 5];
ll cnt[MAX_CYFRA+5][MAX_LEN + 5][MAX_CYFRA + 5];

int GENERATORKI, WAZNE_GENERATORKI;
ll generatorki[MAX_GENERATORKI];
int wazne_generatorki[MAX_GENERATORKI];
int generatorki_konce[MAX_GENERATORKI];
int tnij[MAX_GENERATORKI][MAX_CYFRA + 2];

int ktora(ll x) { 
    int l = 0, r = GENERATORKI-1;
    while (l < r) {
        int m = (l + r) / 2;
        if (generatorki[m] == x) return m;
        else if (generatorki[m] < x) l = m+1;
        else r = m-1;
    }
    return l;
}

int cyfra(ll n) {
    while (n >= 10) {
        ll nowe_n = 1;
        while (n > 0) nowe_n *= n % 10, n /= 10;
        n = nowe_n;
    }

    return (int)n;
}

void preprocess() {
    // Generujemy wszystkie możliwe liczby, do których można trafić po pierwszym mnożeniu cyfr.
    // Jest ich 66061, czyli 'jakoś mało'.
    for (ll a = 1; a <= MAX_N; a *= 2) {
        for (ll b = a; b <= MAX_N; b *= 3) {
            for (ll c = b; c <= MAX_N; c *= 5) {
                for (ll d = c; d <= MAX_N; d *= 7) {
                    generatorki[GENERATORKI++] = d;
                }
            }
        }
	}

    sort(generatorki, generatorki + GENERATORKI);

    for (int g = 0; g < GENERATORKI; g++) {
        ll G = generatorki[g];
        generatorki_konce[g] = cyfra(G);
        if (generatorki_konce[g] != 0) wazne_generatorki[WAZNE_GENERATORKI++] = g;
        for (int c = 0; c <= MAX_CYFRA; c++) {
            if (c == 0 || G % c != 0)
                tnij[g][c] = -1;
            else
                tnij[g][c] = ktora(G / c);
        }
    }

    // Przypadek bazowy: Pojedyńcze cyfry są osiągalne tylko z siebie.
    for (int g = 0; g < MAX_CYFRA; g++) {
        int c = g + 1;
        assert(generatorki[g] == c);
        for (int i = c; i <= MAX_CYFRA; i++) dp[g][1][i] = 1;
    }

    for (int l = 2; l <= MAX_LEN; l++) {
        for (int g = 0; g < GENERATORKI; g++) {
            for (int c = 1; c <= MAX_CYFRA; c++) {
                dp[g][l][c] = dp[g][l][c - 1];
				int g_trimmed = tnij[g][c]; 
                if (g_trimmed != -1) {
                    dp[g][l][c] += dp[g_trimmed][l - 1][9];
                    cnt[generatorki_konce[g]][l][c] += dp[g_trimmed][l-1][c];
                }
            }
        }
    }
}


void solve(ll n) {
    vector<ll> ile(MAX_CYFRA + 1, 0);
    ile[0] = n;

    string s = to_string(n);
    int L = (int)s.size();

    for (int w = 0; w < WAZNE_GENERATORKI; w++) {
        int g = wazne_generatorki[w];
        ll sum = 0;
        // Dodajemy wszystkie liczby, które sa krótsze.
        for (int l = 1; l <= L - 1; l++) {
            sum += dp[g][l][9];
        }

        int g_trimmed = g;
        // Zakładamy, że pierwsza różnica jest na sufiksie o długości L.
        for (int l = L, s_idx = 0; l >= 1; l--, s_idx++) {
            int c = s[s_idx] - '0';

            // Jak mamy już zero w liczbie to wliczymy je z dopełnienia, saga.
            if (c == 0) break;

            // cerr << dbg(g) << dbg(l) << dbg(c-1) << dbg(dp[g][l][c-1]) << endl;
            // Dodajemy wszystkie liczby, które mają mniejszą najbardziej znaczącą cyfrę.
            sum += (c < 1 ? 0 : dp[g_trimmed][l][c - (l == 1 ? 0 : 1)]);

			g_trimmed = tnij[g_trimmed][c];
            if (g_trimmed == -1) break;
            // cerr << dbg(G) << dbg(l) << dbg(c) << dbg(sum) << endl;
        }

        // cerr << dbg(g) << dbg(generatorki[g]) << dbg(generatorki_konce[g]) <<
        // dbg(dp[g][1][generatorki[g]]) << dbg(sum) << endl;
        ile[generatorki_konce[g]] += sum;
        ile[0] -= sum;
    }

    for (int i = 0; i <= MAX_CYFRA; i++) cout << ile[i] << " ";
    cout << "\n";
}

int32_t main() {
    ios_base::sync_with_stdio(0);

    int q;
    cin >> q;
    vector<ll> zapytania(q);
    for (auto &n : zapytania) cin >> n;

    MAX_N = max(10000LL, *max_element(all(zapytania)));
    preprocess();
    
    for (auto n : zapytania) solve(n);
}