1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include "bits/stdc++.h"
using namespace std;
#define all(x) x.begin(),x.end()
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << p.first << " " << p.second; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#define ASSERT(...) 42
#endif
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int oo = 1e9;
unordered_map<ll,array<ll,10>> dp[19] = {};
unordered_map<ll,short> dig;
short getdig(ll v) {
    if(v<10) return v;
    if(dig.count(v)) return dig[v];
    ll cur = 1;
    for(auto c : to_string(v)) {
        cur*=c-'0';
    }
    return dig[v] = getdig(cur);
}
auto operator+(array<ll,10> a, const array<ll,10>& b) {
    for(int j=0;j<10;++j) a[j]+=b[j];
    return a;
}
array<ll,10> solve(ll mult, int left) {
    if(left==0) {
        array<ll,10> res = {};
        res[getdig(mult)]++;
        return res;
    }
    auto it = dp[left].find(mult);
    if(it!=dp[left].end()) return it->second;
    auto& res = dp[left][mult];
    for(int d=0;d<10;++d) {
        res = res+ solve(mult*d,left-1);
        
    }
    return res;
} 
unordered_map<int,array<ll,10>> precomp;
auto solvenonzero(int x) {
    if(x==0) return array<ll,10>{};
    auto it = precomp.find(x);
    if(it!=precomp.end()) return it->second;
    auto& res = precomp[x];
    res=solvenonzero(x-1);
    for(int j=1;j<10;++j) res = res +solve(j,x-1);

    return res;
}

void solve() {
    ll x; cin >> x;
    x++; // strictly smaller
    string n = to_string(x);
    for(auto& i : n) i-='0';
    // take product of those, then bruteforce
    // next digit, then have arbitrary digits...
    ll mult=1;
    array<ll,10> ans = {};
    for(int i=0;i<n.size();++i) {
        for(int j=0;j<n[i];++j) {
            if(i==0 and j==0) continue; // no leading zeros.
            ans = ans+solve(mult*j,n.size()-1-i);
        }
        mult*=n[i];
    }
    ans = ans+solvenonzero(n.size()-1);

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while(t--) solve();
}