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
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;

const int MAXN = 21;
vector<unordered_map<ll,ll>> mapa(MAXN);
unordered_map<string, vector<ll>> rpref;
unordered_map<string, vector<ll>> dp;
vector<ll> pot(MAXN, 0);
vector<ll> pot2(MAXN, 0);

int rekur(ll a){
    if(a < 10) return a;
    ll wynik = 1;
    while(a != 0){
        wynik *= (a % 10);
        a /= 10;
    }
    return rekur(wynik);
}

void potegi(){
    pot[0] = 1;
    pot2[0] = 1;
    for(int i = 1; i < MAXN; i++){
        pot[i] = pot[i - 1] * 10;
        pot2[i] = pot2[i - 1] * 9;
    }
}
 
vector<ll> rev_pref(int x, ll akt){
    string klucz = to_string(x) + "." + to_string(akt);
    if(rpref.count(klucz)) return rpref[klucz];
    vector<ll> odp(10, 0);
    if(x == 0){
        odp[rekur(akt)] = 1;
        return rpref[klucz] = odp;
    }
    else if(akt == 0){
        odp[rekur(0)] = pot[x];
        return rpref[klucz] = odp;
    }
    odp[0] += (pot[x] - pot2[x]);
    for(auto y : mapa[x]) odp[rekur(y.first * akt)] += y.second;
    return rpref[klucz] = odp;
}
 
vector<ll> DP(int idx, ll akt, string s){
    string klucz = to_string(idx) + ".1." + to_string(akt);
    if(dp.count(klucz)) return dp[klucz];
    vector<ll> odp(10, 0);
    if(idx == s.size()){
        odp[rekur(akt)] = 1;
        return dp[klucz] = odp;
    }
    int co = s[idx] - '0';
    int start = 0;
    if(idx == 0) start++;
    for(int i = start; i < co; i++){
        ll x = akt * i;
        vector<ll> part = rev_pref(s.size() - idx - 1, x);
        for(int j = 0; j < 10; j++) odp[j] += part[j];
    }
    if(co >= start){
        ll x = akt * co;
        vector<ll> part = DP(idx + 1, x, s);
        for(int i = 0; i < 10; i++) odp[i] += part[i];
    }
    return dp[klucz] = odp;
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    potegi();
    mapa[0][1] = 1;
    for(int i = 1; i < MAXN; i++){
        for(auto x : mapa[i - 1]){
            for(int j = 1; j <= 9; j++) mapa[i][x.first * j] += x.second;
        }
    }
    vector<vector<ll>> vec(20, vector<ll>(10, 0));
    vector<vector<ll>> w(20, vector<ll>(10, 0));
    for(int i = 1; i <= 19; i++){
        vector<ll> pom(10, 0);
        for(int k = 1; k <= 9; k++){
            vector<ll> part = rev_pref(i - 1, k);
            for(int j = 0; j < 10; j++) pom[j] += part[j];
        }
        vec[i] = pom;
    }
    w[1] = vec[1];
    for(int i = 2; i <= 19; i++){
        w[i] = w[i - 1];
        for(int j = 0; j < 10; j++) w[i][j] += vec[i][j];
    }

    int t;
    cin >> t;
    while(t--){
        dp.clear();
        ll n;
        cin >> n;
        string s = to_string(n);
        vector<ll> odp(10, 0);
        if(s.size() == 1){
            cout << "0 ";
            for(int i = 1; i <= n; i++) cout << "1 ";
            for(int i = n + 1; i < 10; i++) cout << "0 ";
            cout << endl;
            continue;
        }
        else odp = w[s.size() - 1];
        vector<ll> v = DP(0, 1, s);
        for(int i = 0; i < 10; i++) odp[i] += v[i];
        for(int i = 0; i < 10; i++) cout << odp[i] << ' ';
        cout << '\n';
    }
}