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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include <vector>
#include <cstdint>

constexpr int INTERESTING_COUNT = 193;
uint64_t interesting[INTERESTING_COUNT][6] = {{0,0,0,0,1ull,1}, {0,0,0,1,7ull,7}, {0,0,0,2,49ull,8}, {0,0,0,3,343ull,8}, {0,0,1,0,5ull,5}, {0,0,1,1,35ull,5}, {0,0,1,3,1715ull,5}, {0,0,2,1,175ull,5}, {0,1,0,0,3ull,3}, {0,1,0,1,21ull,2}, {0,1,0,2,147ull,6}, {0,1,1,0,15ull,5}, {0,1,2,0,75ull,5}, {0,2,0,0,9ull,9}, {0,2,0,1,63ull,8}, {0,2,0,2,441ull,6}, {0,2,1,1,315ull,5}, {0,2,2,1,1575ull,5}, {0,2,2,3,77175ull,5}, {0,3,0,0,27ull,4}, {0,3,0,1,189ull,4}, {0,3,0,2,1323ull,8}, {0,3,1,0,135ull,5}, {0,3,3,0,3375ull,5}, {0,4,0,0,81ull,8}, {0,4,0,5,1361367ull,8}, {0,4,0,12,1121144263281ull,8}, {0,5,0,0,243ull,8}, {0,5,1,2,59535ull,5}, {0,6,0,0,729ull,2}, {0,7,0,0,2187ull,2}, {0,8,0,2,321489ull,2}, {0,9,0,1,137781ull,8}, {0,10,0,1,413343ull,8}, {0,11,0,0,177147ull,8}, {0,19,0,0,1162261467ull,6}, {1,0,0,0,2ull,2}, {1,0,0,1,14ull,4}, {1,0,0,2,98ull,4}, {1,0,0,3,686ull,6}, {1,0,0,5,33614ull,2}, {1,1,0,0,6ull,6}, {1,1,0,1,42ull,8}, {1,1,0,2,294ull,4}, {1,2,0,0,18ull,8}, {1,2,0,1,126ull,2}, {1,2,0,2,882ull,6}, {1,2,0,3,6174ull,6}, {1,2,0,4,43218ull,8}, {1,2,0,6,2117682ull,6}, {1,3,0,1,378ull,6}, {1,3,0,2,2646ull,6}, {1,4,0,0,162ull,2}, {1,4,0,1,1134ull,2}, {1,4,0,7,133413966ull,6}, {1,5,0,0,486ull,8}, {1,5,0,2,23814ull,8}, {1,5,0,4,1166886ull,8}, {1,6,0,2,71442ull,6}, {1,7,0,2,214326ull,6}, {1,8,0,0,13122ull,2}, {1,8,0,2,642978ull,6}, {1,14,0,3,3281116734ull,6}, {2,0,0,0,4ull,4}, {2,0,0,1,28ull,6}, {2,0,0,3,1372ull,8}, {2,0,0,5,67228ull,6}, {2,1,0,0,12ull,2}, {2,1,0,1,84ull,6}, {2,1,0,3,4116ull,8}, {2,1,0,6,1411788ull,2}, {2,2,0,0,36ull,8}, {2,2,0,2,1764ull,6}, {2,2,0,3,12348ull,8}, {2,4,0,0,324ull,8}, {2,4,0,1,2268ull,8}, {2,4,0,3,111132ull,6}, {2,5,0,0,972ull,2}, {2,7,0,0,8748ull,2}, {2,7,0,1,61236ull,2}, {2,10,0,0,236196ull,6}, {3,0,0,0,8ull,8}, {3,0,0,3,2744ull,6}, {3,0,0,6,941192ull,8}, {3,1,0,0,24ull,8}, {3,1,0,1,168ull,6}, {3,1,0,2,1176ull,8}, {3,2,0,0,72ull,4}, {3,3,0,0,216ull,2}, {3,4,0,0,648ull,8}, {3,5,0,0,1944ull,6}, {3,5,0,3,666792ull,6}, {3,7,0,1,122472ull,6}, {3,11,0,0,1417176ull,8}, {3,11,0,2,69441624ull,6}, {4,0,0,0,16ull,6}, {4,0,0,1,112ull,2}, {4,0,0,2,784ull,6}, {4,0,0,5,268912ull,2}, {4,1,0,0,48ull,6}, {4,2,0,0,144ull,6}, {4,2,0,3,49392ull,6}, {4,3,0,0,432ull,8}, {4,3,0,3,148176ull,6}, {4,4,0,4,3111696ull,2}, {4,5,0,1,27216ull,6}, {4,6,0,0,11664ull,6}, {4,7,0,0,34992ull,6}, {4,9,0,0,314928ull,2}, {4,10,0,2,46294416ull,6}, {5,0,0,0,32ull,6}, {5,0,0,1,224ull,6}, {5,0,0,8,184473632ull,6}, {5,1,0,1,672ull,6}, {5,1,0,3,32928ull,8}, {5,2,0,0,288ull,6}, {5,2,0,2,14112ull,8}, {5,2,0,4,691488ull,8}, {5,3,0,0,864ull,8}, {5,3,0,2,42336ull,8}, {5,4,0,1,18144ull,6}, {5,5,0,3,2667168ull,6}, {5,5,0,6,914838624ull,6}, {5,6,0,0,23328ull,6}, {5,6,0,1,163296ull,6}, {5,10,0,1,13226976ull,6}, {6,0,0,0,64ull,8}, {6,0,0,1,448ull,6}, {6,0,0,8,368947264ull,2}, {6,1,0,0,192ull,8}, {6,1,0,1,1344ull,6}, {6,2,0,4,1382976ull,6}, {6,3,0,0,1728ull,2}, {6,3,0,4,4148928ull,8}, {6,4,0,3,1778112ull,6}, {6,7,0,0,139968ull,6}, {6,8,0,1,2939328ull,6}, {6,10,0,0,3779136ull,8}, {6,27,0,1,3416267673274176ull,6}, {7,0,0,0,128ull,6}, {7,0,0,1,896ull,8}, {7,0,0,2,6272ull,6}, {7,1,0,3,131712ull,8}, {7,2,0,5,19361664ull,6}, {7,3,0,1,24192ull,6}, {7,6,0,0,93312ull,2}, {7,7,0,2,13716864ull,6}, {8,0,0,1,1792ull,2}, {8,1,0,4,1843968ull,6}, {8,2,0,2,112896ull,8}, {8,3,0,5,116169984ull,2}, {8,4,0,3,7112448ull,2}, {9,0,0,4,1229312ull,2}, {9,1,0,4,3687936ull,6}, {9,3,0,0,13824ull,8}, {9,3,0,1,96768ull,6}, {9,4,0,0,41472ull,6}, {9,5,0,0,124416ull,8}, {9,11,0,2,4444263936ull,6}, {10,3,0,3,9483264ull,6}, {10,5,0,1,1741824ull,2}, {10,5,0,5,4182119424ull,8}, {10,6,0,4,1792336896ull,6}, {11,0,0,1,14336ull,2}, {11,2,0,0,18432ull,8}, {11,4,0,1,1161216ull,4}, {11,5,0,4,1194891264ull,8}, {11,6,0,0,1492992ull,6}, {12,0,0,1,28672ull,6}, {12,0,0,8,23612624896ull,6}, {12,4,0,0,331776ull,6}, {13,0,0,0,8192ull,6}, {13,3,0,0,221184ull,6}, {14,1,0,10,13884223438848ull,6}, {15,0,0,3,11239424ull,2}, {15,1,0,3,33718272ull,8}, {15,7,0,0,71663616ull,6}, {16,0,0,2,3211264ull,6}, {16,1,0,2,9633792ull,2}, {17,1,0,0,393216ull,2}, {19,2,0,4,11329339392ull,6}, {20,2,0,0,9437184ull,6}, {20,5,0,1,1783627776ull,8}, {21,4,0,0,169869312ull,6}, {23,2,0,2,3699376128ull,6}, {23,3,0,0,226492416ull,6}, {23,7,0,1,128421199872ull,4}, {24,6,0,6,1438916737499136ull,6}, {25,2,0,1,2113929216ull,6}, {26,3,0,0,1811939328ull,2}, {29,5,0,1,913217421312ull,6}, {34,8,0,0,112717121716224ull,8}, {39,3,0,2,727326941773824ull,8}};

std::vector<int> digits(uint64_t n) {
    std::vector<int> result;
    result.reserve(18);
    while (n > 0) {
        result.push_back(n % 10ull);
        n /= 10ull;
    }
    return result;
}

int numberOfDigits(uint64_t n) {
    int result = 1;
    while (n >= 10) {
        n /= 10;
        ++result;
    }
    return result;
}

uint64_t factorial[21] = {1ull,1ull,2ull,6ull,24ull,120ull,720ull,5040ull,40320ull,362880ull,3628800ull,39916800ull,479001600ull,6227020800ull,87178291200ull,1307674368000ull,20922789888000ull,355687428096000ull,6402373705728000ull,121645100408832000ull,2432902008176640000};

/*
uint64_t factorial(int n) {
    uint64_t res = 1;
    for (int i = 2; i <= n; ++i) {
        res *= static_cast<uint64_t>(i);
    }
    return res;
}
*/

int main() {
    int t;
    std::cin >> t;

    uint64_t n;
    for (int test = 0; test < t; ++test) {
        std::cin >> n;
        uint64_t endCounts[10] = {0};

        std::vector<int> dig = digits(n);
        int counts[10] = {0};
        for (int digit : dig) {
            ++counts[digit];
        }

        int nDig = dig.size();
        for (int i = 0; i < INTERESTING_COUNT; ++i) {
            uint64_t end = interesting[i][5];
            uint64_t result = interesting[i][4];
            if (result > n) { //  || minDigits > nDigits.size()) {
                continue;
            }

            int totalTwos = interesting[i][0];
            int totalThrees = interesting[i][1];

            int onHand[10][2] = {0};

            onHand[5][0] = interesting[i][2];
            onHand[7][0] = interesting[i][3];
            // int minDigits = TODO; // before remembering about sixes, was: (twos + 2)/3 + (threes + 1) / 2 + fives + sevens;

            // 4, 6, 8, 9
            // totalTwos = twos + 2*fours + 3*eights + sixes
            // totalThrees = threes + 2*nines + sixes
            int totalDigitCount = 0;
            for (onHand[8][0] = 0; onHand[8][0] <= totalTwos / 3 /* && onHand[8][0] <= nDig */; ++onHand[8][0]) {
                totalDigitCount = onHand[8][0];
                for (onHand[4][0] = 0; onHand[4][0] <= (totalTwos - 3*onHand[8][0]) / 2 /* && totalDigitCount + onHand[4][0] <= nDig */; ++onHand[4][0]) {
                    totalDigitCount += onHand[4][0];
                    for (onHand[9][0] = 0; onHand[9][0] <= totalThrees / 2 /* && totalDigitCount + onHand[9][0] <= nDig */; ++onHand[9][0]) {
                        totalDigitCount += onHand[9][0];
                        for (onHand[6][0] = 0; onHand[6][0] <= std::min(totalTwos - 3*onHand[8][0] - 2*onHand[4][0], totalThrees - 2*onHand[9][0]) /* && totalDigitCount + onHand[6][0] <= nDig */; ++onHand[6][0]) {
                            onHand[2][0] = totalTwos - 3*onHand[8][0] - 2*onHand[4][0] - onHand[6][0];
                            onHand[3][0] = totalThrees - 2*onHand[9][0] - onHand[6][0];
                            totalDigitCount += onHand[6][0] + onHand[2][0] + onHand[3][0] + onHand[5][0] + onHand[7][0];
                            for (onHand[1][0] = 0; totalDigitCount + onHand[1][0] <= nDig; ++onHand[1][0]) {
                                totalDigitCount += onHand[1][0];
                                if (totalDigitCount == 0) {
                                    totalDigitCount -= onHand[1][0];
                                    continue;
                                }

                                if (totalDigitCount < nDig) {
                                    endCounts[end] += factorial[totalDigitCount] / (factorial[onHand[1][0]] * factorial[onHand[2][0]] * factorial[onHand[3][0]] * factorial[onHand[4][0]] * factorial[onHand[5][0]] * factorial[onHand[6][0]] * factorial[onHand[7][0]] * factorial[onHand[8][0]] * factorial[onHand[9][0]]);
                                } else {
                                    bool same = true;
                                    for (int i = 0; i < 10; ++i) {
                                        if (counts[i] != onHand[i][0]) {
                                            same = false;
                                            break;
                                        }
                                    }
                                    if (same) {
                                        endCounts[end] += 1;
                                    }

                                    for (int i = 0; i < 10; ++i) {
                                        onHand[i][1] = onHand[i][0];
                                    }

                                    for (int ix = nDig - 1; ix >= 0; --ix) {
                                        int d = dig[ix];

                                        for (int i = 0; i < d; ++i) {
                                            if (onHand[i][1] > 0) {
                                                --onHand[i][1];
                                                endCounts[end] += factorial[ix] / (factorial[onHand[1][1]] * factorial[onHand[2][1]] * factorial[onHand[3][1]] * factorial[onHand[4][1]] * factorial[onHand[5][1]] * factorial[onHand[6][1]] * factorial[onHand[7][1]] * factorial[onHand[8][1]] * factorial[onHand[9][1]]);
                                                ++onHand[i][1];
                                            }
                                        }

                                        if (onHand[d][1] == 0) {
                                            break;
                                        } else {
                                            --onHand[d][1];
                                        }
                                    }
                                }
                                totalDigitCount -= onHand[1][0];
                            }
                            totalDigitCount -= onHand[6][0] + onHand[2][0] + onHand[3][0] + onHand[5][0] + onHand[7][0];
                        }
                        totalDigitCount -= onHand[9][0];
                    }
                    totalDigitCount -= onHand[4][0];
                }
                totalDigitCount -= onHand[8][0];
            }

        }

        endCounts[0] = n;
        for (int i = 1; i < 10; ++i) {
            endCounts[0] -= endCounts[i];
        }

        for (int i = 0; i < 10; ++i) {
            std::cout << endCounts[i] << (i == 9? "" : " ");
        }
        std::cout << std::endl;
    }
    return 0;
}