#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
auto &operator<<(auto &o, pair<auto, auto> p) {
    return o << "(" << p.first << ", " << p.second <<")";
}
auto operator<<(auto &o, auto x)-> decltype(x.end(), o) {
    o << "{";int i = 0;
    for(auto e : x) o << ", "+!i++<<e;
    return o <<"}";
}
#define debug(x...) cerr << "["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(x)
#else
#define debug(...) {}
#endif

#define int long long
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define fi first
#define se second
typedef pair <int, int> pii;

constexpr int INF = 1e18;
map <int, int> reduction;

int rdc(int x) {
    if (x < 10) {
        return x;
    }
    int ret = 1;
    while (x > 0) {
        ret *= (x % 10);
        x /= 10;
    }
    return rdc(ret);
}

void generate() {
    int m = 18;

    for (int i=0; i<=m*3; ++i) {
        int dwa = (1ll<<i);
        int trzy = 1;
        int zost1 = (i+2)/3;
        for (int j=0; j <= (m - zost1)*2; ++j) {
            if (dwa * trzy > INF)
                break;

            int zost2 = zost1 + (j+1)/2;
            int piec = 1;

            for (int k=0; k <= m-zost2; ++k) {
                if (dwa * trzy * piec > INF)
                    break;
                
                int zost3 = zost2 + k;
                int siedem = 1;
                for (int l=0; l <= (m-zost3); ++l) {
                    int ilo = dwa * trzy * piec * siedem;
                    if (dwa * trzy * piec * siedem > INF)
                        break;
                    
                    // numbers.push_back({i, j, k, l, dwa*trzy*piec*siedem});
                    reduction[ilo] = rdc(ilo);
                    siedem *= 7;
                }
                piec *= 5;
            }
            trzy *= 3;
        }
    }
}
// czy na styk, ktora cyfra, poteg dwojki, poteg trojki, poteg piatki, poteg siodemki
vector <array<int, 3> > DP[2][19][55][37];
int pot[10][55];
int res[10];
int lim; 

void addtodp(int mniej, int cyfra, int dwa, int trzy, int piec, int siedem, int ile) {
    if (cyfra == lim) {
        int iloczyn = pot[2][dwa] * pot[3][trzy] * pot[5][piec] * pot[7][siedem];
        debug(mniej, cyfra, dwa, trzy, piec, siedem, iloczyn, ile);
        res[reduction[iloczyn]] += ile;
        return ;
    }

    for (auto &[p, s, i] : DP[mniej][cyfra][dwa][trzy]) {
        if (p == piec && s == siedem) {
            i += ile;
            return ;
        }
    } 

    DP[mniej][cyfra][dwa][trzy].push_back({piec, siedem, ile});
}


void calcdp(string x) {
    
    DP[0][0][0][0].push_back({0, 0, 1});
    for (int i=1; i<sz(x); ++i) {
        DP[1][i][0][0].push_back({0, 0, 1});
    }
    for (int cyfra=0; cyfra<sz(x); ++cyfra) {
        for (int mniej=0; mniej<2; ++mniej) {
            for (int dwa=0; dwa<=cyfra*3; ++dwa) {
                for (int trzy=0; trzy<=cyfra*2; ++trzy) {
                    for (auto const &[piec, siedem, ile] : DP[mniej][cyfra][dwa][trzy]) {
                        int iloczyn = pot[2][dwa] * pot[3][trzy] * pot[5][piec] * pot[7][siedem];
                        for (int c=1; c<(mniej ? 10 : (x[cyfra] - '0')); ++c) {
                            if (iloczyn * c > INF) break;
                            if (c == 1) {
                                addtodp(1, cyfra+1, dwa, trzy, piec, siedem, ile);
                            }
                            else if (c == 6) {
                                addtodp(1, cyfra+1, dwa+1, trzy+1, piec, siedem, ile);
                            }
                            else if (c % 2 == 0) {
                                int ii = (c == 8 ? 3 : c/2);
                                addtodp(1, cyfra+1, dwa+ii, trzy, piec, siedem, ile);
                            }
                            else if (c % 3 == 0) {
                                int ii = (c == 3 ? 1 : 2);
                                addtodp(1, cyfra+1, dwa, trzy+ii, piec, siedem, ile);
                            }
                            else if (c == 5) {
                                addtodp(1, cyfra+1, dwa, trzy, piec+1, siedem, ile);
                            }
                            else if (c == 7) {
                                addtodp(1, cyfra+1, dwa, trzy, piec, siedem+1, ile);
                            }
                        }
                        int c = x[cyfra] - '0';
                        if (iloczyn * c > INF || c == 0) continue; 
                        if (mniej==0) {
                            if (c == 1) {
                                addtodp(0, cyfra+1, dwa, trzy, piec, siedem, ile);
                            }
                            else if (c == 6) {
                                addtodp(0, cyfra+1, dwa+1, trzy+1, piec, siedem, ile);
                            }
                            else if (c % 2 == 0) {
                                int ii = (c == 8 ? 3 : c/2);
                                addtodp(0, cyfra+1, dwa+ii, trzy, piec, siedem, ile);
                            }
                            else if (c % 3 == 0) {
                                int ii = (c == 3 ? 1 : 2);
                                addtodp(0, cyfra+1, dwa, trzy+ii, piec, siedem, ile);
                            }
                            else if (c == 5) {
                                addtodp(0, cyfra+1, dwa, trzy, piec+1, siedem, ile);
                            }
                            else if (c == 7) {
                                addtodp(0, cyfra+1, dwa, trzy, piec, siedem+1, ile);
                            }
                        }
                    }
                    DP[mniej][cyfra][dwa][trzy].clear();
                }
            }
        }
    }
}

// czy mniej, czy ma zero, digit
int ZDP[2][2][2][19];
int mazero(string n) {
    int ret = 0;
    ZDP[0][0][0][0] = 1;

    for (int cyfra = 0; cyfra < sz(n); ++cyfra) {
        int bb = n[cyfra] - '0';
        for (int started=0; started<2; ++started) {
            for (int mniej=0; mniej<2; ++mniej) {
                for (int zero=0; zero<2; ++zero){
                    for (int digit=0; digit<(mniej ? 10 : bb); ++digit) {
                        ZDP[started || digit][1][started && (zero || (digit == 0))][cyfra+1] += ZDP[started][mniej][zero][cyfra]; 
                    }
                    if (mniej == 0) {
                        ZDP[started || bb][0][started && (zero || (bb == 0))][cyfra+1] += ZDP[started][0][zero][cyfra];
                    }
                }
            }
        }
    }

    for (int i=0; i<2; ++i) {
        ret += ZDP[1][i][1][sz(n)];
    }
    for (int z=0; z<2; ++z) {

        for (int k=0; k<=sz(n); ++k) {
            for (int i=0; i<2; ++i) {
                for (int j=0; j<2; ++j) {
                    if (z)
                        debug(i, j, k, ZDP[z][i][j][k]);
                    ZDP[z][i][j][k] = 0;
                }
            }
        }
    }
    debug(n, ret);
    return ret;
}

void test() {
    debug("TC______________________");
    // vector <array<int, 5> > numbers;
    // vector <int> redukcja;
    string n; cin>>n;
    lim = sz(n);
    calcdp(n);
    res[0] += mazero(n);
    for (int i=0; i<10; ++i) {
        cout<<res[i]<<" \n"[i==9];
        res[i] = 0;
    }
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int t = 1; cin>>t;
  for (int j=1; j<10; ++j) {
    pot[j][0] = 1;
  }
  for (int i=1; i<55; ++i) {
    for (int j=1; j<10; ++j) {
        pot[j][i] = j * pot[j][i-1];
    }
  }

  generate();

  while (t--) {
    test();
  }
}