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 <iostream>
#include <memory>
#include <unordered_map>

std::unordered_map<int64_t, int8_t> play_memo;
int8_t play(int64_t in) {
    if (in < 10) {
        return in;
    }
    if (play_memo.count(in) > 0) {
        return play_memo[in];
    }
    int64_t curr = in, next = 1;
    while (curr >= 10) {
        next *= curr % 10;
        curr /= 10;
    }
    next *= curr;
    return play_memo[in] = play(next);
}

std::shared_ptr<std::unordered_map<int64_t, int64_t>> set(int64_t in);
std::shared_ptr<std::unordered_map<int64_t, int64_t>> set_inner(int64_t in) {
    auto ret = std::make_shared<std::unordered_map<int64_t, int64_t>>();

    if (in < 10) {
        for (int64_t i = 1; i <= in; ++i) {
            (*ret)[i] = 1;
        }
        return ret;
    }

    int64_t next = 0, mult = 1;
    while (in >= 10) {
        next += mult * (in % 10);
        mult *= 10;
        in /= 10;
    }

    *ret = *set(mult - 1);
    for (int64_t i = 1; i <= in; ++i) {
        auto num = i == in ? next : mult - 1;
        if (num >= mult / 10) {
            auto plus = set(num);
            auto minus = set(mult / 10 - 1);
            for (auto pp: *plus) {
                auto pq = minus->count(pp.first) > 0 ? (*minus)[pp.first] : 0;
                auto pf = pp.first * i;
                if (pf % 10 == 0) {
                    pf = 0;
                }
                auto d = pp.second - pq;
                if (d > 0) {
                    ret->try_emplace(pf, 0);
                    (*ret)[pf] += d;
                }
            }
        }
        ret->try_emplace(0, 0);
        (*ret)[0] += std::min(num + 1, mult / 10);
    }
    return ret;
}
std::shared_ptr<std::unordered_map<int64_t, int64_t>> set(int64_t in) {
#define MEMO(n) if (in == n) { \
    static std::shared_ptr<std::unordered_map<int64_t, int64_t>> x = nullptr; \
    if (!x) { \
        x = set_inner(in); \
    } \
    return x; \
}
    MEMO(99);
    MEMO(999);
    MEMO(9999);
    MEMO(99999);
    MEMO(999999);
    MEMO(9999999);
    MEMO(99999999);
    MEMO(999999999);
    MEMO(9999999999);
    MEMO(99999999999);
    MEMO(999999999999);
    MEMO(9999999999999);
    MEMO(99999999999999);
    MEMO(999999999999999);
    MEMO(9999999999999999);
    MEMO(99999999999999999);
    MEMO(999999999999999999);
#undef MEMO
    return set_inner(in);
}

void go() {
    int64_t in;
    std::cin >> in;

    int64_t res[10] = {};
    auto s = set(in);
    for (auto p: *s) {
        res[play(p.first)] += p.second;
    }

    for (auto r: res) {
        std::cout << r << " ";
    }
    std::cout << "\n";
}

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

    int32_t t;
    std::cin >> t;

    for (int32_t i = 0; i < t; ++i) {
        go();
    }
}