#include <bits/stdc++.h>

#define ndl '\n'
#define ll long long
#define st first
#define nd second
#define debug(x) cout << #x << ": " << x << ndl
#define all(x) (x).begin(), (x).end()

using namespace std;


vector<vector<ll>> pow_mem(10, vector<ll>(70, -1));

ll ppow(ll a, ll b) {
    if(pow_mem[a][b]!=-1) {
        return pow_mem[a][b];
    }
    return pow_mem[a][b] = pow(a,b);
}


struct Hasher {
    size_t operator()(const tuple<int, bool, bool, int, int, int, int>& zmn) const {
        auto [pos, smaller, started, i2, i3, i5, i7] = zmn;
        ll res = 17;
        res = res * 31 + hash<int>()(pos);
        res = res * 31 + hash<bool>()(smaller);
        res = res * 31 + hash<bool>()(started);
        res = res * 31 + hash<int>()(i2);
        res = res * 31 + hash<int>()(i3);
        res = res * 31 + hash<int>()(i5);
        res = res * 31 + hash<int>()(i7);
        return res;
    }
};

struct Hasher2 {
    size_t operator()(const tuple<int, bool, int, int, int, int>& zmn) const {
        auto [pos, started, i2, i3, i5, i7] = zmn;
        ll res = 17;
        res = res * 31 + hash<int>()(pos);
        res = res * 31 + hash<bool>()(started);
        res = res * 31 + hash<int>()(i2);
        res = res * 31 + hash<int>()(i3);
        res = res * 31 + hash<int>()(i5);
        res = res * 31 + hash<int>()(i7);
        return res;
    }
};


struct v_sol{
    v_sol() : v(10, 0) {}
    v_sol(int num) : v(10, 0) {
        this->v[num]++;
    }
    v_sol operator+(const v_sol &other) {
        v_sol newer{};
        for(int i=0;i<10;i++) {
            newer.v[i] = this->v[i] + other.v[i];
        }
        return newer;
    }
    v_sol& operator+=(const v_sol &other) {
        for(int i=0;i<10;i++) {
            this->v[i] += other.v[i];
        }
        return *this;
    }
    friend ostream& operator<<(ostream& os, const v_sol& sol);
    vector<ll> v;
};

ostream& operator<<(ostream& os, const v_sol& sol) {
    for(int i=0;i<=9;i++) {
        os << sol.v[i] <<' ';
    }
    return os;
}


unordered_map<tuple<int, bool, int, int, int, int>, v_sol, Hasher2> global_memo; // ile left, ZAWSZE JEST SMALLER, started, i2, i3, i5, i7


void rob() {
    ll n; cin>>n;
    ll n_cpy = n;
    vector<int> liczba;
    while(n_cpy>0 || (n_cpy==0 && liczba.size()==0)) {
        liczba.push_back(n_cpy%10);
        n_cpy/=10;
    }

    reverse(liczba.begin(), liczba.end());


    unordered_map<tuple<int, bool, bool, int, int, int, int>, v_sol, Hasher> memo;

    function<v_sol(int, bool, bool, int, int, int, int)> digit_dp = [&](int pos, bool smaller, bool started, int i2, int i3, int i5, int i7) {
        tuple<int, bool, bool, int, int, int, int> klucz{pos, smaller, started, i2, i3, i5, i7};
        tuple<int, bool, int, int, int, int> global_klucz{liczba.size()-pos, started, i2, i3, i5, i7};
        // if(i2 == 1 && i5 == 1) {
        //     cout<<"FSDF";
        // }
        if(pos == liczba.size()) {
            if(!started) {
                return memo[klucz] = v_sol();
            }
            if(long long nowa = ppow(2, i2) * ppow(3, i3) * ppow(5, i5) * ppow(7, i7); nowa <= 9) {
                return memo[klucz] = v_sol(nowa);
            } else {
                int new_i2 = 0;
                int new_i3 = 0;
                int new_i5 = 0;
                int new_i7 = 0;
                ll nowa_cpy = nowa;

                while(nowa > 0) {
                    int zz = nowa%10;
                    switch(zz) {
                    case 0: 
                        return memo[klucz] = v_sol(0);
                    case 2:
                        new_i2 += 1;
                        break;
                    case 3:
                        new_i3 += 1;
                        break;
                    case 4:
                        new_i2 += 2;
                        break;
                    case 5:
                        new_i5 += 1;
                        break;
                    case 6:
                        new_i2 += 1;
                        new_i3 += 1;
                        break;
                    case 7:
                        new_i7 += 1;
                        break;
                    case 8:
                        new_i2 += 3;
                        break;
                    case 9:
                        new_i3 += 2;
                        break;
                    default:
                        break;
                    }
                    nowa/=10;
                }

                auto zzzzz = digit_dp(liczba.size(), nowa_cpy < n, true, new_i2, new_i3, new_i5, new_i7);

                if(smaller) {
                    global_memo[global_klucz] = zzzzz;
                }

                return memo[klucz] = zzzzz; 
            }
        }


        if(memo.count(klucz)) {
            return memo[klucz];
        }

        if(smaller && global_memo.count(global_klucz)) {
            return memo[klucz] = global_memo[global_klucz];
        }

        int limit = liczba[pos];
        if(smaller) {
            limit = 9;
        }

        auto sol = v_sol{};

        int new_i2, new_i3, new_i5, new_i7;
        for(ll i=0;i<=limit;i++) {
            if(started && i == 0) {
                if(smaller || 0 < liczba[pos]) {
                    sol.v[0] += pow(10, liczba.size() - pos - 1);
                } else {
                    ll tmpnum = 0;
                    for(int kk = pos+1; kk<liczba.size();kk++) {
                        tmpnum = tmpnum * 10 + liczba[kk];
                    }
                    sol.v[0] += tmpnum+1;
                }
                continue;
            }

            new_i2 = i2;
            new_i3 = i3;
            new_i5 = i5;
            new_i7 = i7;

            switch(i) {
            case 2:
                new_i2 += 1;
                break;
            case 3:
                new_i3 += 1;
                break;
            case 4:
                new_i2 += 2;
                break;
            case 5:
                new_i5 += 1;
                break;
            case 6:
                new_i2 += 1;
                new_i3 += 1;
                break;
            case 7:
                new_i7 += 1;
                break;
            case 8:
                new_i2 += 3;
                break;
            case 9:
                new_i3 += 2;
                break;
            default:
                break;
            }

            sol += digit_dp(pos+1, smaller || (i < liczba[pos]), started || (i > 0), new_i2, new_i3, new_i5, new_i7);
        } 

        if(smaller) {
            global_memo[global_klucz] = sol;
        }

        return memo[klucz] = sol;
    };
    cout<<digit_dp(0, 0, 0, 0, 0, 0, 0)<<'\n';
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
        rob();
}