#include <bits/stdc++.h>

using namespace std;

long long func(long long n)
{
    if (n==0) return 10;
    if (n<10) return n;

    vector<int> cifre;
    long long temp = n;

    for (int d=9; d>=2; --d)
    {
        while (temp%d==0)
        {
            cifre.push_back(d);
            temp/=d;
        }
    }
    if (temp>1) return -1;
    sort(cifre.begin(),cifre.end());
    long long res_val=0;
    for (int d:cifre) {
        if (res_val>LLONG_MAX/10) return -1;
        res_val=res_val*10 + d;
    }
    return res_val;
}

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

    vector<long long> precomputed;
    for (long long a2=1; a2<=LLONG_MAX;)
    {
        for (long long b3=a2; b3<=LLONG_MAX;)
        {
            for (long long c5=b3; c5<=LLONG_MAX;)
            {
                for (long long d7=c5; d7<=LLONG_MAX;)
                {
                    long long m=func(d7);
                    if (m!=-1 && m<=LLONG_MAX)
                        precomputed.push_back(m);

                    if (d7>LLONG_MAX/7) break;
                    d7*=7;
                }
                if (c5>LLONG_MAX/5)break;
                c5*=5;
            }
            if (b3>LLONG_MAX/3) break;
            b3 *= 3;
        }
        if (a2>LLONG_MAX/2) break;
        a2*=2;
    }
    precomputed.push_back(10);
    sort(precomputed.begin(),precomputed.end());

    precomputed.erase(unique(precomputed.begin(), precomputed.end()), precomputed.end());

    int T;
    cin >> T;
    vector<long long> res;
    while (T--)
    {
        long long n;
        cin >> n;
        if (n<10)
            res.push_back(n);

        else
        {
            auto it=upper_bound(precomputed.begin(),precomputed.end(), n);
            res.push_back(distance(precomputed.begin(), it));
        }
    }
    for(auto i:res)cout << i << endl;

    return 0;
}