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

const int N2 = 19;
const int N = 36102;
#define f first
#define s second
using ll = long long;
using pll = pair<ll,ll>;

const int SZ[] = {1,9,41,123,293,595,1088,1833,2911,4402,6404,9021,12369,16570,21731,27550,32845,35696,36100};

int tt;
ll n;
ll dp[N2][N][2];
vector<ll> vec;
vector<ll> vec2;
int go[N][10];
ll ans[10];
int sz;

int get(ll x){
    if(x == 0) return 0;
    ll ret = 1;
    while(x){
        ret *= x%10;
        x /= 10;
    }
    return ret < 10 ? ret : get(ret);
}

void dfs(int v, int lef, ll val){
    if(v == 10){
        vec.push_back(val);
        return;
    }
    
    dfs(v+1, lef, val);
    if(lef) dfs(v, lef-1, val*v);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    vec.push_back(0);
    vec.push_back(1);
    dfs(2, 18, 1);
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for(auto v : vec){
        vec2.push_back(get(v));
    }

    for(int i=0;i<(int)vec.size();i++){
        for(int j=0;j<10;j++){
            if(__builtin_mul_overflow_p(vec[i],j,0LL)) break;
            go[i][j] = lower_bound(vec.begin(),vec.end(),vec[i]*j) - vec.begin();
        }
    }

    sz = vec.size();

    int tt;
    cin >> tt;
    while(tt--){
        cin >> n;
        fill(ans,ans+10,0);
        if(n == (ll)1e18){
            n--;
            ans[0]++;
        }
        ll n2 = n;
        vector<int> dg;
        while(n2){
            dg.push_back(n2%10);
            n2 /= 10;
        }
        reverse(dg.begin(),dg.end());

        for(int i=0;i<=dg.size();i++){
            for(int j=0;j<=SZ[i];j++){
                for(int a=0;a<2;a++){
                    dp[i][j][a] = 0;
                }
            }
        }
        
        for(int i=1;i<=dg[0];i++){
            dp[1][i][i<dg[0]] = 1;
        }
        for(int i=2;i<=(int)dg.size();i++){
            for(int j=1;j<10;j++){
                dp[i][j][1] = 1;
            }
        }

        for(int i=0;i<(int)dg.size();i++){
            for(int j=0;j<=SZ[i];j++){
                for(int a=0;a<2;a++){
                    if(!dp[i][j][a]) continue;
                    for(int c=0;c<=(a?9:dg[i]);c++){
                        dp[i+1][go[j][c]][a||(c<dg[i])] += dp[i][j][a];
                    }
                }
            }
        }

        for(int j=0;j<sz;j++){
            for(int a=0;a<2;a++){
                ans[vec2[j]] += dp[dg.size()][j][a];
            }
        }

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