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
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>
using namespace std;

const int NAX = 1e6 + 5;
vector<int> memo(NAX, -1);
int simulate(long long x) {
	if (x < 10) {
		return x;
	}
	if (x < NAX && memo[x] != -1) {
		return memo[x];
	}
	long long mul = 1;
	while (x) {
		mul *= x % 10;
		x /= 10;
	}
	if (x < NAX) {
		return memo[x] = simulate(mul);
	}
	return simulate(mul);
}

bool ok[25][30][40][60]; // [7][5][3][2]
int expo[10][4];
long long INF = 1.000001e18L;
vector<long long> dp[20][10][25][30][40]; // dp[len][ans][7][5][3][2]

void init() {
	for (int dig = 1; dig < 10; dig++) {
		vector<int> p{7,5,3,2};
		for (int i = 0; i < 4; i++) {
			for (int x = dig; x % p[i] == 0; x /= p[i]) {
				expo[dig][i]++;
			}
		}
	}
	expo[0][1] = expo[0][3] = 1; // 0 = 2 * 5
	long long A = 1;
	for (int d7 = 0; A < INF; d7++, A *= 7) {
		long long B = A;
		for (int d5 = 0; B < INF; d5++, B *= 5) {
			long long C = B;
			for (int d3 = 0; C < INF; d3++, C *= 3) {
				long long D = C;
				for (int d2 = 0; D < INF; d2++, D *= 2) {
					ok[d7][d5][d3][d2] = true;
					int x = simulate(D);
					dp[0][x][d7][d5][d3].resize(61);
					dp[0][x][d7][d5][d3][d2]++;
				}
			}
		}
	}
	// cout << "Y = " << dp[0][3][0][0][1][0] << "\n";
	
	for (int len = 1; len <= 18; len++) {
		for (int x = 0; x < 10; x++) {
			for (int d7 = 0; d7 < 25; d7++) {
				for (int d5 = 0; d5 < 30; d5++) {
					for (int d3 = 0; d3 < 40; d3++) {
						for (int d2 = 0; d2 < (int) dp[len-1][x][d7][d5][d3].size(); d2++) {
							long long me = dp[len-1][x][d7][d5][d3][d2];
							if (me == 0) {
								continue;
							}
							for (int dig = 0; dig < 10; dig++) {
								if (d7 >= expo[dig][0] && d5 >= expo[dig][1] && d3 >= expo[dig][2] && d2 >= expo[dig][3]) {
									vector<long long>& v = dp[len][x][d7-expo[dig][0]][d5-expo[dig][1]][d3-expo[dig][2]];
									int z = d2 - expo[dig][3];
									v.resize(max((int) v.size(), z + 1));
									v[z] += me;
								}
							}
						}
					}
				}
			}
		}
	}
}

int main() {
	init();
	
	
	int T;
	cin >> T;
	while (T--) {
		string s;
		cin >> s;
		int len = (int) s.length();
		vector<long long> ans(10);
		vector<int> pref(4);
		// cout << "X = " << dp[1][3][0][0][0][0] << "\n";
		for (int i = 0; i < len; i++) {
			for (int dig = (i == 0 ? 1 : 0); dig < s[i] - '0'; dig++) {
				for (int x = 0; x < 10; x++) {
					//  dp[len][ans][7][5][3][2]
					if (pref[3] + expo[dig][3] < (int) dp[len-1-i][x][pref[0]+expo[dig][0]][pref[1]+expo[dig][1]][pref[2]+expo[dig][2]].size()) {
						ans[x] += dp[len-1-i][x][pref[0]+expo[dig][0]][pref[1]+expo[dig][1]][pref[2]+expo[dig][2]][pref[3]+expo[dig][3]];
					}
				}
			}
			if (i != 0) {
				for (int dig = 1; dig < 10; dig++) {
					for (int x = 0; x < 10; x++) {
						// cerr << len-1-i << " " << x << " ";
						// for (int j = 0; j < 4; j++) cerr << expo[dig][j] << " ";
						// cerr << "\n";
						if (expo[dig][3] < (int) dp[len-1-i][x][expo[dig][0]][expo[dig][1]][expo[dig][2]].size()) {
							ans[x] += dp[len-1-i][x][expo[dig][0]][expo[dig][1]][expo[dig][2]][expo[dig][3]];
						}
						// cerr << "ok\n";
					}
				}
			}
			for (int j = 0; j < 4; j++) {
				pref[j] += expo[s[i]-'0'][j];
			}
		}
		ans[simulate(stoll(s))]++;
		
		for (long long x : ans) {
			cout << x << " ";
		}
		cout << "\n";
	}
}