#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <deque>
#include <tuple>
#include <bitset>
#include <array>

using namespace std;

#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define x first
#define y second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

template <typename T>
inline void hash_combine(std::size_t& seed, const T& value) {
    seed ^= std::hash<T>{}(value) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

inline uint32_t makeKey(uint32_t a, uint32_t b, uint32_t c, uint32_t d) {
    return (a) | (b << 8) | (c << 16) | (d << 24);
}


struct prime {
    uint32_t key;

    prime(uint32_t a, uint32_t b, uint32_t c, uint32_t d) : key(makeKey(a, b, c, d)) {}

    prime() : key(0) {}

    uint32_t getA() const { return key & 0xFF; }
    uint32_t getB() const { return (key >> 8) & 0xFF; }
    uint32_t getC() const { return (key >> 16) & 0xFF; }
    uint32_t getD() const { return (key >> 24) & 0xFF; }
};

bool operator==(const prime &lhs, const prime &rhs) {
    return lhs.key == rhs.key;
}

namespace std {
    template <>
    struct hash<prime> {
        std::size_t operator()(const prime &pk) const {
            return std::hash<uint32_t>()(pk.key);
        }
    };
}

vll main_numbers;
unordered_map<ll, ll> main_numbers_root;

prime prime_hash[10];
unordered_map<prime, ll> prime_frequency[20];
unordered_map<prime, ll> prime_root;

ll cache_ans_zero[20][10];
unordered_map<prime, std::array<ll, 10>> cache_ans[20];
ll ans[10];

void generate_main_numbers(ll n, ll max_base){
    main_numbers.pb(n);
    if(n < max_base){
        ll digit = n % 10;
        n *= 10;
        for(ll i=max(1ll, digit); i<10; i++){
            generate_main_numbers(n + i, max_base);
        }
    }
}

ll fact[20];

ll len(ll n){
    ll l = 0ll;
    while(n>0){
        l++;
        n/=10;
    }
    return l;
}

prime convert_to_prime(ll n){
    ll cur_n = n;
    prime p = {0, 0, 0, 0};
    bool was_zero = false;
    while(cur_n>0){
        ll digit = cur_n%10;
        if(digit == 0ll){
            was_zero = true;
        }
    
        prime digit_p = prime_hash[digit];
        p = prime(p.getA() + digit_p.getA(), p.getB() + digit_p.getB(), p.getC() + digit_p.getC(), p.getD() + digit_p.getD());

        cur_n/=10;
    }

    if(was_zero){
        p = {0, 0, 0, 0};
    }
    return p;
}

ll multiplicative_root(ll n){
    if(main_numbers_root.find(n) != main_numbers_root.end()){
        return main_numbers_root[n];
    }

    if(len(n)==1){
        main_numbers_root[n]=n;
        return n;
    }

    ll mul = 1;
    ll cur_n = n;
    while(cur_n>0){
        mul *= cur_n%10;
        cur_n/=10;
    }
    ll root = multiplicative_root(mul);
    main_numbers_root.try_emplace(n, root);
    return root;
}

void primes_root_freq(ll n){
    ll l = len(n);
    ll frequency = fact[l];
    unordered_map<int, int> digits;

    ll cur_n = n;
    while(cur_n>0){
        digits[cur_n%10]++;
        cur_n/=10;
    }
    for(int i=1; i<10; i++){
        frequency /= fact[digits[i]];
    }

    prime p = convert_to_prime(n);
    prime_frequency[l][p] += frequency;
    prime_root.try_emplace(p, multiplicative_root(n));
}


void cache_prefix_zero(int l){
    for(int i=1; i<=l; i++){
        for (auto& it: prime_frequency[i]) {
            cache_ans_zero[i][prime_root[it.first]] += it.second;
        }
    }
    for(int i=2; i<=l; i++){
        for(int j=2; j<10; j++){
            cache_ans_zero[i][j]+=cache_ans_zero[i-1][j];
        }
    }
}


void solve_prefix(ll n, int l){
    prime p = convert_to_prime(n);

    if(l==0){
        ans[prime_root[p]]++;
        return;
    }

    ll digit;
    ll cur_n = n;
    while(cur_n>0){
        ll digit = cur_n%10;
        if(digit == 0ll){
            return;
        }
        cur_n /= 10;
    }

    if(cache_ans[l].find(p) != cache_ans[l].end()){
        std::array<ll, 10> cur_ans = cache_ans[l][p];
        for(int i=2; i<10; i++){
            ans[i] += cur_ans[i];
        }
        return;
    }

    std::array<ll, 10> cur_ans;
    for(int i=0; i<10; i++){
        cur_ans[i] = 0;
    }

    for (auto& it: prime_frequency[l]) {
        prime cur_p = p;
        cur_p = prime(cur_p.getA() + it.first.getA(), cur_p.getB() + it.first.getB(), cur_p.getC() + it.first.getC(), cur_p.getD() + it.first.getD());
        cur_ans[prime_root[cur_p]] += it.second;
    }

    cache_ans[l][p] = cur_ans;
    for(int i=2; i<10; i++){
        ans[i] += cur_ans[i];
    }
}



void solve(ll n){
    int l = len(n);

    for(int i=0; i<10; i++){
        ans[i] = cache_ans_zero[l-1][i];
    }

    ll cur_n = n;
    int cur_l = 0;
    while(cur_n>0){
        ll digit = cur_n%10;
        cur_n/=10;
        cur_n*=10;

        for(int i=1; i<digit; i++){
            solve_prefix(cur_n+i, cur_l);
        }
        cur_n /= 10;
        cur_l++;
    }
    
    solve_prefix(n, 0);

    ll one = 1;
    ans[1] = 0;
    while(one <= n){
        ans[1]++;
        one*=10;
        one+=1;
    }

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



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

    int t;
    cin >> t;
    ll max_base=0;

    vll q;

    for(int i=0; i<t; i++){
        ll n;
        cin >> n;
        q.pb(n);
        max_base=max(max_base, n);
    }

    prime_hash[0] = {0, 0, 0, 0};
    prime_hash[1] = {0, 0, 0, 0};
    prime_hash[2] = {1, 0, 0, 0};
    prime_hash[3] = {0, 1, 0, 0};
    prime_hash[4] = {2, 0, 0, 0};
    prime_hash[5] = {0, 0, 1, 0};
    prime_hash[6] = {1, 1, 0, 0};
    prime_hash[7] = {0, 0, 0, 1};
    prime_hash[8] = {3, 0, 0, 0};
    prime_hash[9] = {0, 2, 0, 0};


    main_numbers_root.reserve(8000000);
    prime_root.reserve(50000);
    for(int i=1; i<20; i++){
        prime_frequency[i].reserve(50000);
    }

    for(ll i=1; i<10; i++){
        generate_main_numbers(i, max_base);
    }

    fact[0]=1;
    for(int i=1; i<20; i++){
        fact[i] = fact[i-1]*i;
    }

    for(auto & a: main_numbers){
        primes_root_freq(a);
    }

    cache_prefix_zero(18);

    for(int i=0; i<t; i++){
        solve(q[i]);
    
        for(int i=0; i<10; i++){
            cout << ans[i] << " ";
        }
        cout << "\n";
    }

    return 0;
}