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
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

unordered_map<ll, int> Convert; 
unordered_map<ll, ll> Helper[20];
unordered_map<ll, bool> Temp;
unordered_map<ll, array<ll, 10>> Values[20];

vector<ll> Memorize[20];

int Find(ll x)
{
    ll y = x;
    while(y > 9) {
        ll val = y;
        y = 1;
        while(val > 0) {
            y *= (val % 10);
            val /= 10;
        }
    }
    return Convert[x] = y;
}

void Preprocess()
{
    Helper[0][1] = 1;
    for(int i = 1; i <= 18; i++) {
        for(ll j = 0; j < 10; j++) {
            for(auto e : Helper[i-1])
                Helper[i][e.first * j] += e.second;
        }
    }
    for(auto e : Helper[18])
        Find(e.first);

    Memorize[0].resize(10, 0);
    for(int i = 1; i <= 18; i++) {
        Memorize[i].resize(10, 0);
        for(ll j = 1; j < 10; j++) {
            for(auto e : Helper[i-1]) 
                Memorize[i][Convert[j * e.first]] += e.second;
        }

        for(int j = 0; j < 10; j++)
            Memorize[i][j] += Memorize[i-1][j];
    }

    for(int i = 1; i <= 18; i++) {
        for(ll j = 1; j < 10; j++) {
            for(auto e : Helper[i-1])
                Temp[e.first * j] = true;
        }
        for(auto e1 : Temp) {
            for(auto e2 : Helper[18 - i])
                Values[18-i][e1.first][Convert[e1.first * e2.first]] += e2.second;
        }
        Temp.clear();
    }
}

void Digitize(vector<ll>& Digits, ll n)
{
    while(n > 0) {
        Digits.push_back(n % 10);
        n /= 10;
    }
    reverse(Digits.begin(), Digits.end());
}

vector<ll> Solution(10, 0);
vector<ll> Digits;

void Solve(ll n)
{
    Digitize(Digits, n);

    ll mult = 1;
    int len = Digits.size();
    for(int j = 0; j < 10; j++)
        Solution[j] = Memorize[len-1][j];

    for(int i = 0; i < Digits.size(); i++) {
        for(int j = 0; j < Digits[i]; j++) {
            if(j == 0 && i == 0)
                continue;
            
            for(int k = 0; k < 10; k++)
                Solution[k] += Values[len-i-1][mult*j][k];
        }
        mult *= Digits[i];
    }
    Solution[Convert[mult]]++;

    for(int i = 0; i < 10; i++) {
        cout << Solution[i] << " ";
        Solution[i] = 0;
    }
    cout << "\n";
    Digits.clear();
}

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

    Preprocess();

    int t;
    ll n;
    cin >> t;
    while(t --> 0) {
        cin >> n;
        Solve(n);
    }
    return 0;
}