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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <map>
using namespace std;

//#define DEBUG(x) x
//#define CALC_TIME

#ifndef DEBUG
    #define DEBUG(x)
#endif

#define REP(x,n) for(int x=0;x<(n);++x)
#define VAR(x,n) __typeof(n) x = (n)
#define FOREACH(x,c) for(VAR(x, (c).begin()); x != (c).end(); ++x)
#define CONTAINS(x,elem) ((x).find(elem) != (x).end())

const int MAX_DIGITS = 19;

long long calc(long long i) {
    if (i<10)
        return i;
    else if(i<100) {
        return calc((i/10) * (i%10));
    }
    long long product = 1;
    while (product && i) {
        product *= i % 10;
        i /= 10;
    }
    return calc(product);
}

long long result[10];
const long long POW_10[] = {
    1,
    10,
    100,
    1000,
    10000,
    100000,
    1000000,
    10000000,
    100000000,
    1000000000,
    10000000000,
    100000000000,
    1000000000000,
    10000000000000,
    100000000000000,
    1000000000000000,
    10000000000000000,
    100000000000000000,
    1000000000000000000};

map<long long, long long> products[MAX_DIGITS];

void precalc(int currentDigits, int targetDigits) {
    long long currentMax=POW_10[currentDigits];
    while (currentDigits < targetDigits) {
        DEBUG(cerr << "calc currentDigit="<<currentDigits<<endl;)
        const map<long long, long long>& oldProducts = products[currentDigits];
        map<long long, long long>& newProducts = products[currentDigits+1];
        newProducts[0] += currentMax*9/10;
        
        for(map<long long, long long>::const_iterator it = oldProducts.begin(); it != oldProducts.end(); ++it) {
            for(int i=1;i<=9;++i) {
                newProducts[it->first * i] += it->second;
            }       
        }
        currentMax *= 10;
        DEBUG(
            long long sumsum = 0;
            cerr << "products after currentDigit="<<currentDigits<<endl;
            for(map<long long, long long>::const_iterator it = newProducts.begin(); it != newProducts.end(); ++it) {
                cerr << it->first << "=" << it->second << " ";
                sumsum += it->second;
            }
            cerr << "; sum=" << sumsum << endl;
            cerr << "newProducts["<<currentDigits+1<<"] contains " << newProducts.size() << " entries" << endl;
        )
        ++currentDigits;
    }
}

int soFarMaxDigits=0;
int currentDigits[MAX_DIGITS];

void solve(long long n) {

    int noOfDigits = 0;
    for(long long m=n; m; m/=10, ++noOfDigits) {
        currentDigits[noOfDigits] = m%10;
    }
    --noOfDigits;
    if (noOfDigits > soFarMaxDigits) {
        precalc(soFarMaxDigits, noOfDigits);
        soFarMaxDigits = noOfDigits;
    }

    //first phase - calc results for <1, 99..99> which is still smaller than n
    for (int i = 1; i <= noOfDigits; ++i) {
        const map<long long, long long>& currentDigitProducts = products[i];
        for(map<long long, long long>::const_iterator it = currentDigitProducts.begin(); it != currentDigitProducts.end(); ++it) {
            result[calc(it->first)] += it->second;
        }
        DEBUG(
            cerr<<"first phase step ["<<i<<"]; result so far:";
            REP(x,10) cout << " " << result[x];
            cerr << endl;
        )
    }

    //second phase - reach subsequent leading digits
    long long prefixProduct = 1;
    for (int currentDigitIndex = noOfDigits; prefixProduct && currentDigitIndex >= 0; --currentDigitIndex) {
        int currentDigit = currentDigits[currentDigitIndex];

        const map<long long, long long>& currentDigitProducts = products[currentDigitIndex];
        for(map<long long, long long>::const_iterator it = currentDigitProducts.begin(); it != currentDigitProducts.end(); ++it) {
            switch (currentDigit) {
                case 9: result[calc(it->first * 8 * prefixProduct)] += it->second;
                case 8: result[calc(it->first * 7 * prefixProduct)] += it->second;
                case 7: result[calc(it->first * 6 * prefixProduct)] += it->second;
                case 6: result[calc(it->first * 5 * prefixProduct)] += it->second;
                case 5: result[calc(it->first * 4 * prefixProduct)] += it->second;
                case 4: result[calc(it->first * 3 * prefixProduct)] += it->second;
                case 3: result[calc(it->first * 2 * prefixProduct)] += it->second;
                case 2: result[calc(it->first * 1 * prefixProduct)] += it->second;
            }
        }
        DEBUG(
            cerr<<"processing digit  ["<<currentDigitIndex<<"] = "<< currentDigit <<"; current prefix is: " << prefixProduct << endl;
            cerr << "result so far:";
            REP(x,10) cout << result[x] << " ";
            cerr << endl;
        )
        prefixProduct *= currentDigit;
    }

    //last digit
    ++result[calc(prefixProduct)];

    //cheat
    long long remaining = n;
    for(int i=1;i<10;++i)
        remaining -= result[i];
    DEBUG(cerr << "cheating - replacing result[0]="<<result[0]<<" with "<<remaining<<endl;)
    result[0] = remaining;
}

#ifdef CALC_TIME
#include <ctime>
#endif

int main() {
    ios_base::sync_with_stdio(0);
    int t;
    long long n;
    cin>>t;
    products[0][1] = 1;
#ifdef CALC_TIME
    clock_t begin = clock();
#endif
    REP(i,t) {
        cin>>n;
        solve(n);
            
        long long sumsum = 0;
        REP(x,10) {
            cout << result[x] << " ";
            sumsum += result[x];
            result[x] = 0;
        }
        cout << endl;
    }
#ifdef CALC_TIME
    cerr << "TIME: " << float(clock()-begin)/CLOCKS_PER_SEC << " s " << endl;
#endif
}