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
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=(a);i<(n);i++)
#define per(i,a,n) for (int i=(n)-1;i>=(a);i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef long double db;
mt19937 mrand(1111); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

vector<ll> dig;
array<ll,10> dp[22][37333],ret[22];
int go[37333][11];
int m;
array<ll,10> operator +(const array<ll,10> &a,const array<ll,10> &b) {
	array<ll,10> c;
	rep(i,0,10) c[i]=a[i]+b[i];
	return c;
}
ll f(ll x) {
	ll y=1;
	while (x) y=y*(x%10),x/=10;
	return y;
}
void print(const array<ll,10> &a) {
	rep(k,0,10) {
		printf("%lld%c",a[k]," \n"[k==9]);
	}
}
int _;
int main() {
	dig.pb(0);
	dig.pb(1);
	rep(i,1,19) {
		vector<ll> ndig;
		for (auto x:dig) rep(j,0,10) ndig.pb(x*j);
		sort(all(ndig)); ndig.erase(unique(all(ndig)),ndig.end());
		dig=ndig;
	}
	m=SZ(dig);
	rep(i,0,SZ(dig)) {
		rep(j,0,10) {
			ll w=dig[i]*j;
			auto it=lower_bound(all(dig),w);
			if (it!=dig.end()&&*it==w) {
				go[i][j]=it-dig.begin();
			} else {
				go[i][j]=-1;
			}
		}
	}
	rep(i,0,SZ(dig)) {
		ll w=dig[i]; while (w>=10) w=f(w);
		dp[0][i][w]=1;
	}
	rep(b,0,18) {
		rep(i,0,SZ(dig)) rep(j,0,10) if (go[i][j]!=-1)
			dp[b+1][i]=dp[b+1][i]+dp[b][go[i][j]];
	}
	rep(b,1,19) rep(j,1,10) {
		ret[b]=ret[b]+dp[b-1][go[1][j]];
	}
	for (scanf("%d",&_);_;_--) {
		ll n;
		scanf("%lld",&n);
		++n;
		VI d;
		array<ll,10> ans;
		rep(i,0,10) ans[i]=0;
		while (n) d.pb(n%10),n/=10;
		reverse(all(d));
		rep(b,1,SZ(d)) ans=ans+ret[b];
		int num=1;
		rep(i,0,SZ(d)) {
			rep(j,(i==0)?1:0,d[i]) {
				ans=ans+dp[SZ(d)-i-1][go[num][j]];
			}
			num=go[num][d[i]];
		}
		print(ans);
	}
}