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
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const LL N=1e18;
LL n;
vector<LL>A;
map<LL,int>nxt;
LL ans[10],pw10[19];
map<tuple<int,LL,LL>,int>F;
inline void init(){
    A.emplace_back(0);
    for(LL a=1;a<=N;a*=2)
        for(LL b=a;b<=N;b*=3)
            for(LL c=b;c<=N;c*=5)
                for(LL d=c;d<=N;d*=7)A.emplace_back(d);
    sort(A.begin(),A.end());
    for(LL x:A)
        if(x<10)nxt[x]=x;
        else{
            LL z=x,y=1;
            while(z)y*=z%10,z/=10;
            nxt[x]=nxt[y];
        }
    sort(A.begin(),A.end(),[&](LL x,LL y){
        return nxt[x]>nxt[y];
    });
    while(!nxt[A.back()])A.pop_back();
    pw10[0]=1;
    for(int i=1;i<19;++i)pw10[i]=pw10[i-1]*10;
}
inline LL solve(int k,LL x,LL n){
    n=min(n,pw10[k+1]-1);
    if(k<0)return x==1;
    if(F.count(make_tuple(k,x,n)))return F[make_tuple(k,x,n)];
    LL z=0;
    for(int c=1;c<10;++c)if(x%c==0&&n>=pw10[k]*c)
        z+=solve(k-1,x/c,n-pw10[k]*c);
    return F[make_tuple(k,x,n)]=z;
}
inline void MAIN(){
    cin>>n;
    fill(ans,ans+10,0);
    for(LL x:A)for(int i=0;i<17;++i)ans[nxt[x]]+=solve(i,x,n);
    ans[0]=n;
    for(int i=1;i<10;++i)ans[0]-=ans[i];
    for(int i=0;i<10;++i)cout<<ans[i]<<" \n"[i==9];
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    init();
    int t=1;cin>>t;while(t--)MAIN();
    return 0;
}
/*
*/