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

const int MAX2 = 54, MAX3 = 36, MAX5 = 18, MAX7 = 18, MAX_DIGITS = 18;
const ull MAX_N = 1e18;

ull n, t, res[10], dp[MAX2 + 1][MAX3 + 1][MAX5 + 1][MAX7 + 1][MAX_DIGITS + 1];
int ile[10][10];

vector<tuple<ull, ull, ull, ull>> factors[10];

ull p(ull x, ull k) {
    if(k == 0) return 1;
    ull val = p(x, k/2);
    if(k % 2 == 0) return val * val;
    return val * val * x;
}

ull calculate(ull x){
    while(x >= 10) {
        ull temp = 1;
        while(x){
            temp *= x % 10;
            x /= 10;
        }
        x = temp;
    }
    return x;
}

vector<int> d(ull x) {
    vector<int> res;
    while(x) {
        res.push_back(x % 10);
        x /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    for(int i = 1 ; i<=9 ; i++) {
        for(int j = 2 ; j<=9 ; j++) {
            int res = 0;
            int x = i;
            while(x % j == 0) {
                res++;
                x /= j;
            }
            ile[i][j] = res;
        }
    }

    for(ull i = 0 ; i<=MAX2 ; i++) {
        for(ull j = 0 ; j<=MAX3; j++) {
            for(ull k = 0 ; k<=MAX5 ; k++) {
                for(ull q = 0 ; q<=MAX7 ; q++) {
                    ull val = p(2, i) * p(3, j) * p(5, k) * p(7, q);
                    if(val > MAX_N) {
                        break;
                    }
                    if(ceil(i/3) + ceil(j/2) + k + q > MAX_DIGITS) {
                        break;
                    }
                    factors[calculate(val)].push_back({i, j, k, q});
                }
            }
        }
    }

    dp[0][0][0][0][0] = 1;
    for(int d = 1 ; d <= MAX_DIGITS ; d++) {
        for(int i = 0 ; i <= MAX2 && ceil(i/3) <= d ; i++) {
            for(int j = 0 ; j <= MAX3 && ceil(i/3) + ceil(j/2) <= d; j++) {
                for(int k = 0 ; k <= MAX5 && ceil(i/3) + ceil(j/2) + k <= d ; k++) {
                    for(int q = 0 ; q <= MAX7 && ceil(i/3) + ceil(j/2) + k + q <= d ; q++) {
                        for(int num = 1 ; num <= 9 ; num++) {
                            int ile2 = ile[num][2], ile3 = ile[num][3], ile5 = ile[num][5], ile7 = ile[num][7];
                            if(i >= ile2 && j >= ile3 && k >= ile5 && q >= ile7) {
                                dp[i][j][k][q][d] += dp[i - ile2][j - ile3][k - ile5][q - ile7][d - 1];
                            }
                        }
                    }
                }
            }
        }
    }

    cin>>t;
    while(t--) {
        cin>>n;

        ull sum = 0;

        res[0] = 0;
        if(n == MAX_N) {
            res[0] = 1;
            n--;
        }

        vector<int> digits = d(n);

        for(int i = 1 ; i<=9 ; i++) {
            res[i] = 0;
            for(auto [a1, b1, c1, d1] : factors[i]) {
                int a = a1, b = b1, c = c1, d = d1;
                for(int x = 1 ; x<digits.size() ; x++) {
                    res[i] += dp[a][b][c][d][x];
                }
                for(int x = 0 ; x < digits.size() ; x++) {
                    int digit = digits[x];
                    if(digit == 0) {
                        break;
                    }
                    for(int j = 1 ; j < digit ; j++) {
                        int ile2 = ile[j][2], ile3 = ile[j][3], ile5 = ile[j][5], ile7 = ile[j][7];
                        if(a >= ile2 && b >= ile3 && c >= ile5 && d >= ile7) {
                            res[i] += dp[a - ile2][b - ile3][c - ile5][d - ile7][digits.size() - x - 1];
                        }
                    }
                    int ile2 = ile[digit][2], ile3 = ile[digit][3], ile5 = ile[digit][5], ile7 = ile[digit][7];
                    a -= ile2;
                    b -= ile3;
                    c -= ile5;
                    d -= ile7;
                }
            }
            sum += res[i];
        }
        res[0] += n - sum - 1;
        res[calculate(n)]++;

        for(int i = 0 ; i<=9 ; i++) {
            cout<<res[i]<<" ";
        }
        cout<<"\n";
    }
}