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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
typedef pair <LL,LL> pll;
#define pb push_back
const int INF = 2147483647;
const int N = 1000005;

LL a, res[N], tab[N][10], bat[N][10], pa, rx[10];
int i, z, g1[N], g[N], b, j, bb, a1, a2, a3;
VI v[10];
vector<LL> vvA[N], vvB[N], vvC[N];
map<LL, LL> m1, m2;


int get(LL a) {
	if (a < 10) return a;
	LL b = 1;
	while (a > 0) {
		b *= (a % 10);
		a /= 10;
	}
	return get(b);
}

int get1(int a) {
	int b = 1;
	for (int i=0;i<6;i++) {
		b *= (a % 10);
		a /= 10;
	}
	return b;
}

LL step(LL a) {
	if (a < 10) return a;
	LL b = 1;
	while (a > 0) {
		b *= (a % 10);
		a /= 10;
	}
	return b;
}

int getC(LL a) {
	while (a >= 1000000) a = step(a);
	return g[a];
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for (i=0;i<1000000;i++) {
	g1[i] = get1(i);
	g[i] = get(i);
	m1[g1[i]]++;
}
for (auto &w1 : m1) for (auto &w2 : m1) m2[w1.first * w2.first] += w1.second * w2.second;

for (i=1;i<1000000;i++) {
	b = step(i);
	if (vvA[b].size() == 0) {
		for (j=0;j<10;j++) vvA[b].pb(0);
		for (auto& w : m1) vvA[b][getC(w.first * b)] += w.second;
	}
	for (j=0;j<10;j++) {
		bat[i][j] = bat[i - 1][j] + vvA[b][j];
	}
}

for (i=1;i<1000000;i++) {
	b = step(i);
	if (vvB[b].size() == 0) {
		for (j=0;j<10;j++) vvB[b].pb(0);
		for (auto& w : m2) vvB[b][getC(w.first * b)] += w.second;
	}
	for (j=0;j<10;j++) tab[i][j] = tab[i - 1][j] += vvB[b][j];	
}

for (i=1;i<1000000;i++) rx[g[i]]++;


cin >> z;
while (z--) {
	cin >> a;
	for (auto& w : m1) vvC[w.first].clear();
	for (i=0;i<10;i++) res[i] = 0;
	pa = a;
	a3 = a % 1000000;
	a /= 1000000;
	a2 = a % 1000000;
	a /= 1000000;
	a1 = a;
	if (a1 > 0) {
		for (i=0;i<10;i++) res[i] += tab[a1 - 1][i];	
		b = step(a1);
		for (i=0;i<a2;i++) {
			bb = step(i);
			if (vvC[bb].size() == 0) {
				for (j=0;j<10;j++) vvC[bb].pb(0);
				for (auto& w : m1) vvC[bb][getC(w.first * b * bb)] += w.second;
			}
			for (j=0;j<10;j++) res[j] += vvC[bb][j];
		}		
		for (i=0;i<10;i++) res[i] += bat[999999][i];
		for (i=0;i<=a3;i++) res[getC(pa - i)]++;
		for (i=0;i<10;i++) res[i] += rx[i];
		
	} else if (a2 > 0) {
		for (i=0;i<10;i++) res[i] += bat[a2 - 1][i];
		for (i=0;i<=a3;i++) res[getC(pa - i)]++;
		for (i=0;i<10;i++) res[i] += rx[i];
	} else for (i=1;i<=a3;i++) res[g[i]]++;	
	for (i=0;i<10;i++) cout << res[i] << " ";
	cout << endl;
}
return 0;
}