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
#include <bits/stdc++.h>
#define int long long

using namespace std;
struct nums {
    int res[10] = {0};
};
unordered_map<int, nums>dp[1009];
unordered_map<int, int>digit;
int og(int x){
    if (x < 10) return x;
    if(digit.count(x)) return digit[x];
    int y = x, z = 1;
    while(y){
        z *= y%10;
        y/=10;
    }
    digit[x] = og(z);
    return digit[x];
}
int hahs(int it, bool onpref, bool beg, bool zero, int x){
    return (1LL*it << 40)|(1LL*onpref << 39)|(1LL*beg << 38)|(1LL*zero << 37)|x;
}
void calc(const string& num, int it, bool onpref, bool beg, bool zero, int x, int t){
    int H = hahs(it, onpref, beg, zero, x);
    if(it == num.size()){
        nums n;
        if(!beg) return;
        if(zero) n.res[0] = 1;
        else n.res[og(x)] = 1;
        dp[t][H] = n;
    }
    if(dp[t].count(H)) return;
    nums n;
    int mx = 9; if(onpref) mx = num[it]-'0';
    for(auto i = 0; i <= mx; ++i){
        bool ONPREF = (onpref && (i == mx));
        bool BEG = beg || (i != 0);
        bool ZERO = zero || (!i && beg);
        int X = x; if(BEG && !ZERO) X *= i;
        calc(num, it+1, ONPREF, BEG, ZERO, X, t);
	int H1 = hahs(it+1, ONPREF, BEG, ZERO, X);
	nums m = dp[t][H1];
        for(int j = 0; j < 10; ++j) n.res[j] += m.res[j];
    }
    dp[t][H] = n;
}
int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
	string num = to_string(n);
	int H = hahs(0, 1, 0, 0, 1);
	calc(num, 0, 1, 0, 0, 1, t);
        for(auto i = 0; i < 10; ++i) cout << dp[t][H].res[i] << " ";
        cout << endl;
    }
}