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
#include <cstdio>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define INT(x) int x; scanf("%d", &x)
#define LLG(x) LL x; scanf("%lld", &x)

typedef long long LL;

LL res[10000000][10];
LL res1[10];
int p[10000000];
int ii = 1;

LL play(LL x) {
	if (x < 10) return p[x] = x;
	LL z = x;
	do {
		LL y = 1;
		while (z) {
			y *= z % 10;
			z /= 10;
		}
		z = y;
	} while (z >= 10000000);
	if (x < 10000000) p[x] = p[z];
	return p[z];
}

void test() {
	LLG(n);
	while (ii <= n && ii < 10000000) {
		REP(i,10) res[ii][i] = res[ii - 1][i];
		++res[ii][play(ii)];
		++ii;
	}
	if (n < ii) {
		REP(i,10) {
			if (i) printf(" ");
			printf("%lld", res[n][i]);
		}
		printf("\n");
		return;
	}
	REP(i,10) res1[i] = res[ii - 1][i];
	int jj = ii;
	while (jj <= n) {
		++res1[play(jj)];
		++jj;
	}
	REP(i,10) {
		if (i) printf(" ");
		printf("%lld", res1[i]);
	}
	printf("\n");
}

int main() {
	INT(t);
	REP(tt,t) test();
}