//
// Mateusz Pietrowcow
//
 
#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;

using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using ii = pair<int,int>;
using uii = pair<uint,uint>;
using pll = pair<ll,ll>;
using pull = pair<ull,ull>;
using ld = long double;
using pld = pair<ld,ld>;
#define int128 __int128_t
#define uint128 __uint128_t

#define pbds __gnu_pbds
#define cxx __gnu_cxx

#define MOD 1000000007
#define MODLL 1000000007LL
#define MODULL 1000000007ULL

// best primes in the galaxy
#define MOD1 1000000007LL
#define MOD2 1000000403LL
#define MOD3 1000000787LL
#define MOD4 1000001447LL

#define INF 1'000'000
#define INFLL 1'000'000'000'000'000'000LL
#define INFULL 1'000'000'000'000'000'000ULL
#define timeNow() (chrono::high_resolution_clock::now().time_since_epoch().count())
#define all(x) x.begin(),x.end()
#define len(x) (int)(x.size())
#define lenl(x) (ll)(x.size())
#define inRange(x,a,b) (a <= x && x <= b)
#define fir first
#define sec second
#define self(x,y,z) y = x(y,z)


template <typename X, typename Y, typename Z>
using gp_hashmap = pbds::gp_hash_table<X,Y,Z,equal_to<X>,pbds::direct_mask_range_hashing<>,pbds::linear_probe_fn<>,pbds::hash_standard_resize_policy<pbds::hash_exponential_size_policy<>,pbds::hash_load_check_resize_trigger<>,true>>;
template <typename X, typename Y, typename Z>
using gp_hashmap_safe = pbds::cc_hash_table<X,Y,Z,equal_to<X>,pbds::direct_mod_range_hashing<>,pbds::hash_standard_resize_policy<pbds::hash_prime_size_policy,pbds::hash_load_check_resize_trigger<>,true>>;

template <typename X, typename Y, typename Z>
using cc_hashmap = pbds::cc_hash_table<X,Y,Z,equal_to<X>,pbds::direct_mask_range_hashing<>,pbds::hash_standard_resize_policy<pbds::hash_exponential_size_policy<>,pbds::hash_load_check_resize_trigger<>,true>>;
template <typename X, typename Y, typename Z>
using cc_hashmap_safe = pbds::cc_hash_table<X,Y,Z,equal_to<X>,pbds::direct_mod_range_hashing<>,pbds::hash_standard_resize_policy<pbds::hash_prime_size_policy,pbds::hash_load_check_resize_trigger<>,true>>;

template <typename X, typename Y, typename Z>
using indexed_set = pbds::tree<X, Y, Z, pbds::rb_tree_tag, pbds::tree_order_statistics_node_update>;


struct chash
{
    size_t operator()(const int& a) const
    {
        const static int rng = (int)timeNow() ^ (int)(ull)(make_unique<char>().get());
        return a ^ rng;
    }
};

const int D = 19;

vector<int> t;
ull n;
int d;

namespace cnt0
{
    ull dp[D][3][2];
    // added non-zero, smaller

    ull solve()
    {
        memset(dp, 0, sizeof(dp));

        ull res = 0;

        dp[0][0][0] = 1;

        for (int i = 0; i <= d; i++)
        {
            if (i == d)
            {
                res += dp[i][2][0] + dp[i][2][1];
                break;
            }

            for (int j = 1; j < 10; j++)
            {
                dp[i + 1][2][1] += dp[i][2][1];
                dp[i + 1][1][1] += dp[i][0][1] + dp[i][1][1];

                if (t[i] > j) 
                    dp[i + 1][1][1] += dp[i][1][0] + dp[i][0][0],
                    dp[i + 1][2][1] += dp[i][2][0];
                else if (t[i] == j) 
                    dp[i + 1][1][0] += dp[i][1][0] + dp[i][0][0],
                    dp[i + 1][2][0] += dp[i][2][0];
            }

            // adds leading zero
            dp[i + 1][0][1] += dp[i][0][1];
            dp[i + 1][0][(t[i] > 0)] += dp[i][0][0];

            // adds in zero
            dp[i + 1][2][1] += dp[i][2][1] + dp[i][1][1];
            dp[i + 1][2][(t[i] > 0)] += dp[i][2][0] + dp[i][1][0];
        }

        return res;
    }
}

namespace values
{
    constexpr ull pr[4] = {2, 3, 5, 7};
    ull p[4][60];
    int cost[10][4];
    unsigned char dp[60][60][60][60];

    array<int, 4> tmp;

    char _get(array<int, 4> q)
    {
        #define dp_val dp[q[0]][q[1]][q[2]][q[3]]

        if (dp_val < 10)
            return dp_val;

        ull r = 1;
        for (int i = 0; i < 4; i++)
            r *= p[i][q[i]];

        tmp[0] = tmp[1] = tmp[2] = tmp[3] = 0;
        for (auto i : to_string(r))
            for (int j = 0; j < 4; j++)
                tmp[j] += cost[i-'0'][j];
        
        if (tmp[0] >= INF) 
            return dp_val = 0;
        if (tmp == q) 
            return dp_val = (char)r;
        return dp_val = _get(tmp);
    }

    inline char get(array<int, 3> q)
    {
        for (int i = 0; i < 2; i++)
            tmp[i] = q[i];
        tmp[2] = 0, tmp[3] = q[2];
        return _get(tmp);
    }

    inline char get2(array<int, 3> q)
    {
        for (int i = 0; i < 3; i++)
            tmp[i+1] = q[i];
        tmp[0] = 0;
        return _get(tmp);
    }

    void init()
    {
        memset(dp, (1<<8)-1, sizeof(dp));

        for (int i = 0; i < 4; i++)
        {
            p[i][0] = 1;

            for (int j = 1; j < 60; j++)
                p[i][j] = p[i][j - 1] * pr[i];
        }

        cost[0][0] = INF;
        for (int i = 1; i < 10; i++)
            for (int j = 0; j < 4; j++)
                cost[i][j] = [&]()
                {
                    int x = i, r = 0;
                    while (x % (int)pr[j] == 0)
                        x /= (int)pr[j], r++;
                    return r;
                }();
    }
}

namespace cntrest
{
    ull dp[D][D*3][D*2][D][2][2];
    // added, smaller

    int cost[10][3], val[3] = {2, 3, 7};
    vector<ull> res(10, 0);

    struct info
    {
        int dl;
        array<int, 3> l;
        bool added, smaller;
    };

    queue<info> rm;

    void init()
    {
        fill(all(res), 0);

        for (int i = 1; i < 10; i++)
            for (int j = 0; j < 3; j++)
                cost[i][j] = [&]()
                {
                    int x = i, r = 0;
                    while (x % val[j] == 0)
                        x /= val[j], r++;
                    return r;
                }();
    }

    vector<ull> solve()
    {
        init();

        queue<info> q;

        dp[0][0][0][0][0][0] = 1;
        q.push({0, {0,0,0}, false, false});

        while (!q.empty())
        {
            auto curr = q.front();
            q.pop();

            rm.push(curr);

            #define dp_info(x) dp[x.dl][x.l[0]][x.l[1]][x.l[2]][x.added][x.smaller]

            if (curr.dl == d)
            {
                if (!curr.added) 
                    continue;

                res[values::get(curr.l)] += dp_info(curr);

                continue;
            }

            if (!curr.added)
            {
                info nx = curr;
                nx.dl++;
                nx.smaller |= (0 < t[curr.dl]);
                dp_info(nx) += dp_info(curr);
                q.emplace(nx);
            }

            for (int i = 1; i < 10; i++)
            {
                if (i > t[curr.dl] && !curr.smaller)
                    break;
                if (i == 5) continue;

                info nw = curr;
                nw.dl++;
                nw.added = true;
                nw.smaller |= (i < t[curr.dl]);
                for (int j = 0; j < 3; j++)
                    nw.l[j] += cost[i][j];
                
                ull* x = &dp_info(nw);

                if (*x == 0)
                    q.emplace(nw);
                *x += dp_info(curr);
            }
        }

        while (rm.size())
        {
            dp_info(rm.front()) = 0;
            rm.pop();
        }

        return res;
    }
}

namespace cnt5
{
    ull dp[D][2*D][D][D][2][2][2];

    struct info
    {
        int dl;
        array<int, 3> l;
        bool added, smaller, par;
    };

    queue<info> rm;

    #define dp_info2(x) dp[x.dl][x.l[0]][x.l[1]][x.l[2]][x.added][x.smaller][x.par]

    vector<ull> solve()
    {
        vector<ull> res = {0,0};
        queue<info> q;

        dp[0][0][0][0][0][0][0] = 1;
        q.push({0, {0,0,0}, false, false, false});

        while (!q.empty())
        {
            auto curr = q.front();
            q.pop();

            rm.push(curr);

            if (curr.dl == d)
            {
                if (!curr.added || curr.l[1] == 0) 
                    continue;
                if (curr.par) res[0] += dp_info2(curr);
                else res[!!values::get2(curr.l)] += dp_info2(curr);
                continue;
            }

            if (!curr.added)
            {
                info nx = curr;
                nx.dl++;
                nx.smaller |= (0 < t[curr.dl]);
                dp_info2(nx) += dp_info2(curr);
                q.emplace(nx);
            }

            for (int i = 1; i < 10; i++)
            {
                if (i > t[curr.dl] && !curr.smaller)
                    break;

                info nw = curr;
                nw.dl++;
                nw.added = true;
                nw.smaller |= (i < t[curr.dl]);
                nw.par |= (i % 2 == 0);

                if (i % 2)
                {
                    if (i == 9) nw.l[0] += 2;
                    else if (i != 1) nw.l[i / 2 - 1] += 1; 
                }
                
                ull* x = &dp_info2(nw);

                if (*x == 0)
                    q.emplace(nw);
                *x += dp_info2(curr);
            }
        }

        while (rm.size())
        {
            dp_info2(rm.front()) = 0;
            rm.pop();
        }

        return res;
    }
}

namespace sol
{
    ll res[10];

    void read()
    {
        cin >> n;

        fill(res,res+10,0);

        if (n == INFULL)
        {
            res[0]++;
            n--;
        }

        t.clear();
        for (auto i : to_string(n))
            t.push_back(i-'0');
        d = len(t);
    }
    
    void solve()
    {
        res[0] += cnt0::solve();

        auto tmp = cnt5::solve();
        res[0] += tmp[0], res[5] += tmp[1];

        int wsk = 0;
        for (auto i : cntrest::solve())
            res[wsk++] += i;

        for (int i = 0; i < 10; i++)
            cout << res[i] << ' ';
        cout << '\n';
    }
};
 
int main()
{
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);

    values::init();

    int z;
    cin >> z;

    while (z--)
    {
        sol::read();
        sol::solve();
    }
}