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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pii> vpii;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef long double ld;
typedef unordered_map<int, int> umii;
typedef vector<pair<ll,ll>> vpll;
typedef tuple<int,int,int> tp;
typedef unsigned long long ull;
const ll MOD = 1e9+696969;

unordered_map<ll,int> fin;

int dig(ll n)
{
    if(n<10)return (int)n;
    if(fin.find(n)!=fin.end())
    return fin[n];
    ll prod =1;
    ll tmp =n;
    while(tmp >0)
    {
        int d=tmp%10;
        prod *=d;
        tmp /=10;
    }

    int res = dig(prod);
    fin[n]=res;
    return res;
}

vi d;
unordered_map<string, unordered_map<ll, ull>> mdp;
unordered_map<ll, ull> dp(int pos, int t, int st, ll prod)
{
    if(pos == (int)d.size())
    {
        unordered_map<ll, ull> ret;
        if(st) ret[prod] = 1;
        return ret;
    }

    string s = to_string(pos) + "_" + to_string(t) + "_" + to_string(st) + "_" + to_string(prod);
    if(mdp.count(s)) 
    return mdp[s];

    unordered_map<ll, ull> res;

    int lim = (t ? d[pos] : 9);
    for (int i = 0; i <= lim; i++)
    {
        int nt = t and (i == lim);
        int ns = st;
        ll np = prod;
        if(!st)
        {
            if(i == 0) np = 1;
            else 
            { 
                ns = 1; 
                np = i; 
            }
        } 
        else 
        np *= i;
        
        auto sub = dp(pos+1, nt, ns, np);
        for(auto &pr: sub)
        res[pr.first] += pr.second;
    }
    return mdp[s] = res;
}

vector<ull> solve1(ll n) 
{
    string s = to_string(n);
    d.clear();

    for(auto c : s) d.push_back(c - '0');
    mdp.clear();

    auto mp = dp(0, 1, 0, 1LL);

    vector<ull> ans(10, 0);



    for(auto pr : mp)
    ans[dig(pr.first)] += pr.second;

    return ans;
}
void solve()
{
    int n;
    cin >> n;
    vll ns(n);
    for(int i=0; i<n; ++i)
    cin >> ns[i];

    for(auto x: ns)
    {
        auto res=solve1(x);
        for(int i=0; i<10; ++i)
        cout << res[i] << (i==9? "\n" : " ");
    }
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
    return 0;
}