#include <bits/stdc++.h>

using namespace std;

#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;
unordered_set<int> first;

int p(int x){
    int c = 1;
    while(x){
        c *= (x%10);
        x /= 10;
    }

    return c;
}

const int maxx = INT64_MAX;
bool veliko(int a, int b, int c, int d){

    int aa = a/3;

    int bb = b / 2;

    if (a % 3 == 2){
        if (b % 2)
            ++bb;
        ++aa;
    } else if (a % 3 == 1){
        ++aa;
    } else {
        if (b % 2) ++bb;
    }


    if (aa + bb + c + d > 18) return 1;
    return 0;
}

int calc(int a, int b, int c, int d){
    vi s;

    for (int i = 0; i < a/3; ++i)
        s.push_back(8);

    for (int i = 0; i < b/2; ++i){
        s.push_back(9);
    }

    if (a%3 == 1 && b%2){
        s.push_back(6);
    } else {
        if (a % 3 == 1){
            s.push_back(2);
            if (b % 2) s.push_back(3);
        }
        if (a % 3 == 2){
            if (b % 2){
                s.push_back(6);
                s.push_back(2);
            } else {
                s.push_back(4);
            }
        }
        if (a % 3 == 0){
            if (b % 2)
                s.push_back(3);
        }
    }
    for (int i = 0; i < c; ++i)
        s.push_back(5);
    for (int i = 0; i < d; ++i)
        s.push_back(7);

    sort(s.begin(), s.end());

    int x = 0;
    for (int t : s)
        x = (10* x) + t;
    return max(1ll, x);
}

vi f;

void init(){
    int p2 = 1, p3 = 1, p5 = 1, p7 = 1;
    first.insert(10);
    first.insert(1);
    for (int i2 = 0; i2 <= 54; ++i2){
        for (int i3 = 0; i3 <= 54; ++i3){
            for (int i5 = 0; i5 <= 54; ++i5){
                for (int i7 = 0; i7 <= 54; ++i7){
                    int x = calc(i2,i3,i5,i7);
                    int y = p2 * p3 * p5 * p7;
                    //first[y] = x;
                    first.insert(x);
                 //   cout << "ZA " << y << ' ' << x << '\n';
                    if (veliko(i2,i3,i5,i7+1)) break;
                    p7  *= 7;
                }
                p7 = 1;

                if (veliko(i2,i3,i5+1,0)) break;
                p5 *= 5;
            }
            p5 = 1;

            if (veliko(i2,i3+1,0,0)) break;
            p3 *= 3;
        }
        p3 = 1;

        if (veliko(i2+1,0,0,0)) break;
        p2 *= 2;
    }

    for (int x : first)
        f.push_back(x);
    sort(f.begin(), f.end());

}

int solve(int n){
    int ind = upper_bound(f.begin(), f.end(), n) - f.begin();
    return ind;
}

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    
    init();
    int test = 101;
    cin >> test;

    while(test--){
        int n;
        cin >> n;

    //    cout << test << ' ';
      //  cout << (int)s.size() << ' ';
        cout << solve(n) << '\n';
    }
}