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

using namespace std;

typedef long long ll;

constexpr int K = 18;
ll factorial[K+1];
vector<pair<ll,ll>> prod_cnt[K+1]; // prod_cnt[K] := zbiór par {prod_i, cnt_i}, gdzie cnt_i := #liczb K-cyfrowych (z zerami wiodącymi) o iloczynie cyfr prod_i
vector<tuple<array<char, 10>, ll, ll>> digit_cnts;
ll cnt_all[K+1][10]; // cnt[K][D][W] := #liczb K-cyfrowych (bez zer wiodących), kończących zabawę na W

void find_sets(array<char,10> cur_digit_cnt, ll cur_prod, ll cur_comb, int cur_digit, int digits_left){
    if(cur_digit > 9){
        if(digits_left > 0)
            return;
        digit_cnts.push_back({cur_digit_cnt, cur_prod, cur_comb});
        return;
    }
    for(int cnt_cur=0; cnt_cur<=digits_left; ++cnt_cur){
        find_sets(cur_digit_cnt, cur_prod, cur_comb/factorial[cnt_cur], cur_digit+1, digits_left-cnt_cur);
        cur_digit_cnt[cur_digit]++;
        cur_prod *= cur_digit;
    }
}

int len(ll x){
    int res=1;
    while(x>=10){
        x/=10;
        ++res;
    }
    return res;
}

constexpr ll mdig_root(ll x, ll prod=1){
    return x*prod <= 9 ? prod*x : x<=9 ? mdig_root(prod*x, 1) : mdig_root(x/10, prod*(x%10));
}

int kth(ll x, int k){
    while(k-->1) x/=10;
    return x%10;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    factorial[0] = 1;
    for(int k=1; k<=K; ++k)
        factorial[k] = factorial[k-1]*k;

    prod_cnt[0] = {{1,1}};
    for(int d=0; d<=9; ++d){
        cnt_all[1][d] = 1;
        prod_cnt[1].push_back({d,1});
    }


    for(int k=2; k<K; ++k){
        digit_cnts.clear();
        find_sets(array<char,10>{},1,factorial[k],0,k);
        map<ll,ll> map_prod_cnt;
        for(auto &[arr,prod,comb] : digit_cnts)
            map_prod_cnt[prod] += comb;
        for(auto &&[prod,cnt] : map_prod_cnt)
            prod_cnt[k].push_back({prod,cnt});
        // cout << prod_cnt[k].size() << endl; 
    }
    // return 0;

    for(int k=2; k<=K; ++k){
        for(int d=1; d<=9; ++d){
            for(auto &[prod,cnt] : prod_cnt[k-1]){       
                cnt_all[k][mdig_root(d*prod)] += cnt;
            }
        }
    }
    cnt_all[1][0] = 0;
    int q;
    cin >> q;
    map<tuple<char,char,ll>, array<ll,10>> pref_ans;
    while(q--){
        ll num;
        cin >> num;
        const int num_len = len(num);
        ll cur_product=1;
        array<ll,10> ans{};
        array<ll,10> cur_ans{};
        // Liczby (num_len)-cyfrowe
        for(int k=num_len; k>=1; --k){
            for(int d=k==num_len ? 1 : 0; d<=kth(num,k)-1; ++d){
                if(pref_ans.count(make_tuple(k,d,cur_product))>0){
                    const auto & _pref_ans = pref_ans[make_tuple(k,d,cur_product)];
                    for(int i=0; i<10; ++i)
                        ans[i] += _pref_ans[i];
                    continue;
                }
                cur_ans.fill(0);
                int r;
                for(const auto &[prod,cnt] : prod_cnt[k-1]){      
                    r = mdig_root(cur_product*d*prod);
                    cur_ans[r] += cnt;
                    ans[r] += cnt;
                }
                
                pref_ans[make_tuple(k,d,cur_product)] = cur_ans;
            }
            cur_product *= kth(num,k);
        }
        // Mniej-cyfrowe liczby
        for(int l=num_len-1; l>=1; --l){
            for(int w=0; w<=9; ++w){
                ans[w] += cnt_all[l][w];
            }
        }

        ++ans[mdig_root(num)];
        for(int i=0; i<=9; ++i)
            cout << ans[i] << " ";
        cout << "\n";
    }

}