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
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
using namespace std;

vector <int> znac;
vector <int> goat;
vector <int> sus;
vector <int> ans;
vector <int> cyfry;
int sil[20];
unordered_map <int, int> mp[20];
unordered_map <int, int> vis;

void fikumiku(int n){
    if(vis[n]>=0) return;
    if(n<10){
        vis[n]=n;
        return;
    }
    int x=1, y=n;
    while(y>0){
        x*=y%10;
        y/=10;
    }
    fikumiku(x);
    vis[n]=vis[x];
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, a, b, i, j, t, p, ilo, ile, il, k, m, x;
    sil[0]=1;
    for(i=1; i<=18; i++){
        sil[i]=sil[i-1]*i;
    }
    for(k=1; k<=18; k++){
        sus.resize(k+8);
        for(i=0; i<sus.size(); i++){
            if(sus.size()-i>8){
                sus[i]=0;
            }
            else{
                sus[i]=1;
            }
        }
        mp[k][1]++;
        if(vis[1]==0){
            vis[1]=-1;
            znac.push_back(1);
        }
        while(next_permutation(sus.begin(), sus.end())){
            j=1;
            ilo=1;
            ile=sil[k];
            il=0;
            for(i=0; i<sus.size(); i++){
                if(sus[i]==1){
                    j++;
                    ile/=sil[il];
                    il=0;
                }
                else{
                    ilo*=j;
                    il++;
                }
            }
            ile/=sil[il];
            if(vis[ilo]==0){
                vis[ilo]=-1;
                znac.push_back(ilo);
            }
            mp[k][ilo]+=ile;
            //cout << k << ' ' << ilo << ' ' << ile << '\n';
        }
    }
    mp[0][1]=1;
    sort(znac.begin(), znac.end());
    k=0;
    for(i=0; i<znac.size(); i++){
        fikumiku(znac[i]);
        if(vis[znac[i]]!=0){
            goat.push_back(znac[i]);
            //cout << znac[i] << ' ' << vis[znac[i]] << '\n';
            k++;
        }
    }
    //cout << k << ' ' << znac.size() << '\n';
    cin >> t;
    m=goat.size();
    while(t--){
        cin >> n;
        ans.clear();
        ans.resize(10);
        cyfry.clear();
        x=n;
        while(x>0){
            cyfry.push_back(x%10);
            x/=10;
        }
        reverse(cyfry.begin(), cyfry.end());
        for(j=1; j<cyfry.size(); j++){
            for(i=0; i<m; i++){
                ans[vis[goat[i]]]+=mp[j][goat[i]];
            }
        }
        ilo=1;
        for(j=0; j<cyfry.size(); j++){
            il=0;
            for(i=1; i<cyfry[j]; i++){
                il+=ilo;
                for(k=0; k<m; k++){
                    if(goat[k]%il!=0) continue;
                    x=goat[k]/il;
                    ans[vis[goat[k]]]+=mp[cyfry.size()-j-1][x];
                }
            }
            ilo*=cyfry[j];
            if(ilo==0) break;
        }
        for(i=0; i<m; i++){
            if(goat[i]==ilo){
                ans[vis[goat[i]]]++;
            }
        }
        k=0;
        for(i=1; i<10; i++){
            k+=ans[i];
        }
        cout << n-k << ' ';
        for(i=1; i<10; i++){
            cout << ans[i];
            if(i<9) cout << ' ';
        }
        cout << '\n';
    }
    return 0;
}