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

#define llong long long
#define ldouble long double
#define uint unsigned int
#define ulong unsigned long long

using namespace std;

typedef array<llong, 10> Arr;

string s;
int L;

int calc_res(llong prod) {
    while (prod >= 10) {
        llong newProd = 1;
        llong temp = prod;
        while (temp > 0) {
            int d = temp % 10;
            newProd *= d;
            temp /= 10;
        }
        prod = newProd;
    }
    return (int) prod;
}

struct state {
    int pos, tight, started;
    llong prod;
    bool operator==(const state &other) const {
        return pos == other.pos && tight == other.tight && started == other.started && prod == other.prod;
    }
};

struct hassh {
    size_t operator()(const state &st) const {
        return (((st.pos * 2 + st.tight) * 2 + st.started) * 1000000 + st.prod);
    }
};

unordered_map<state, Arr, hassh> memo;

const Arr& dp(state& st) {
    if (st.pos == L) {
        static Arr res;
        fill(res.begin(), res.end(), 0);
        if (!st.started) return res;
        int final = calc_res(st.prod);
        res[final] = 1;
        return res;
    }

    if (memo.find(st) != memo.end()) return memo[st];

    auto& ans = memo[st];
    fill(ans.begin(), ans.end(), 0);
    int limit = (st.tight ? s[st.pos] - '0' : 9);

    for (int d = 0; d <= limit; d++) {
        int ntight = (st.tight && d == limit) ? 1 : 0;
        int nstarted = st.started;
        llong nprod = st.prod;

        if (!st.started) {
            if (d == 0) {
                nstarted = 0;
                nprod = 1;
            } 
            else {
                nstarted = 1;
                nprod = d;
            }
        } 
        else {
            if (d == 0) {
                nprod = 0;
            } 
            else {
                nprod = st.prod * d;
            }
        }
        state nst = {st.pos + 1, ntight, nstarted, nprod};
        const Arr& sub = dp(nst);
        for (int i = 0; i < 10; i++) {
            ans[i] += sub[i];
        }
    }

    return ans;
}

void solve() {
    llong n; cin >> n;
    s = to_string(n);
    L = s.size();
    memo.clear();
    state st = {0, 1, 0, 1};
    auto res = dp(st);
    for (int i = 0; i < 10; i++) cout << res[i] << " ";
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int t; cin >> t;

    while (t--) solve();

    return 0;
}