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

using namespace std;

#define _DEBUG
#ifdef _DEBUG
template<typename T1, typename T2> auto& operator<<(ostream& o, pair<T1, T2> a) { return o << "(" << a.first << ", " << a.second << ")"; }
template<typename T, typename OS> auto& operator<<(OS& o, T a) { o << "{"; for (auto b : a) o << b << ", "; return o << "}"; }
#define dbg(x...) cerr << "[" #x "]: ", [](auto... args) { ((cerr << args << ", "),...) << "\n"; }(x)
#else
#define dbg(...)
#endif

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define F first
#define S second

using ll = long long;
using ld = long double;
using pll = pair<ll,ll>;
using vi = vector<int>;

ll g(ll x) {
    while(x > 9) {
        ll y = 1;
        while(x>0) {
            y *= (x%10);
            x /= 10;
        }
        x = y;
    }
    return x;
}

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

    vector<vector<map<ll,ll>>> cnt(19, vector<map<ll,ll>>(10));
    for(ll i = 0 ; i < 10 ; ++i) cnt[0][i][i] = 1;

    for(ll len = 1 ; len < 19 ; ++len) {
        for(ll i = 0 ; i < 10 ; ++i) {
            for(ll j = 0 ; j < 10 ; ++j) {
                for(auto [p, q] : cnt[len-1][i]) {
                    cnt[len][j][j*p] += q;
                }
            }
        }
    }

    for(ll len = 0 ; len < 19 ; ++len) {
        for(ll i = 1 ; i < 10 ; ++i) {
            for(auto [p, q] : cnt[len][i-1])
                cnt[len][i][p] += q;
        }
    }

    unordered_map<ll,ll> f;
    for(auto [p, q] : cnt[18][9]) {
        f[p] = g(p);
    }

    vector<map<ll,ll>> dp(19);
    for(ll i = 1 ; i < 10 ; ++i) dp[0][i] = 1;
    for(ll len = 1 ; len < 19 ; ++len) {
        for(ll i = 0 ; i < 10 ; ++i) {
            for(auto [p, q] : dp[len-1]) {
                dp[len][p*i] += q;
            }
            if(i>0) dp[len][i]++;
        }
    }

    vector<vector<ll>> res(19, vector<ll>(10));
    for(ll len = 0 ; len < 19 ; ++len) {
        for(auto [p, q] : dp[len]) {
            res[len][f[p]] += q;
        }
    }

    ll t;
    cin >> t;
    while(t--) {
        ll n, xd; cin >> n;
        xd = n;
        vector<ll> v;
        while(n>0) {
            v.emplace_back(n%10);
            n /= 10;
        }
        reverse(all(v));

        vector<ll> ans(10);
        ans[g(xd)]++;
        ll mult = v[0];
        for(auto [p, q] : cnt[sz(v)-1][v[0]-1]) {
            ans[f[p]] += q;
        }
        for(auto [p, q] : cnt[sz(v)-1][0]) {
            ans[f[p]] -= q;
        }
        for(ll i = 1 ; i < sz(v) ; ++i) {
            if(v[i] != 0) {
                for(auto [p, q] : cnt[sz(v)-i-1][v[i]-1]) {
                    ans[f[p*mult]] += q;
                }
            }

            mult *= v[i];
        }
        if(sz(v) > 1) for(ll i = 0 ; i < 10 ; ++i) ans[i] += res[sz(v)-2][i];
        for(int i = 0 ; i < 10 ; ++i) cout << ans[i] << " ";
        cout << '\n';
    }

    return 0;
}