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
130
131
132
133
134
135
136
137
138
139
140
141
#include <bits/stdc++.h>
using namespace std;

#define inf 1000000000000000000ll;
typedef long long ll;

//vector <ll> nums = {1, 7, 49, 343, 5, 35, 1715, 175, 3, 21, 147, 15, 75, 9, 63, 441, 315, 1575, 77175, 27, 189, 1323, 135, 3375, 81, 1361367, 1121144263281, 243, 59535, 729, 2187, 321489, 137781, 413343, 177147, 1162261467, 2, 14, 98, 686, 33614, 6, 42, 294, 18, 126, 882, 6174, 43218, 2117682, 378, 2646, 162, 1134, 133413966, 486, 23814, 1166886, 71442, 214326, 13122, 642978, 3281116734, 4, 28, 1372, 67228, 12, 84, 4116, 1411788, 36, 1764, 12348, 324, 2268, 111132, 972, 8748, 61236, 236196, 8, 2744, 941192, 24, 168, 1176, 72, 216, 648, 1944, 666792, 122472, 1417176, 69441624, 16, 112, 784, 268912, 48, 144, 49392, 432, 148176, 3111696, 27216, 11664, 34992, 314928, 46294416, 32, 224, 184473632, 672, 32928, 288, 14112, 691488, 864, 42336, 18144, 2667168, 914838624, 23328, 163296, 13226976, 64, 448, 368947264, 192, 1344, 1382976, 1728, 4148928, 1778112, 139968, 2939328, 3779136, 3416267673274176, 128, 896, 6272, 131712, 19361664, 24192, 93312, 13716864, 1792, 1843968, 112896, 116169984, 7112448, 1229312, 3687936, 13824, 96768, 41472, 124416, 4444263936, 9483264, 1741824, 4182119424, 1792336896, 14336, 18432, 1161216, 1194891264, 1492992, 28672, 23612624896, 331776, 8192, 221184, 13884223438848, 11239424, 33718272, 71663616, 3211264, 9633792, 393216, 11329339392, 9437184, 1783627776, 169869312, 3699376128, 226492416, 128421199872, 1438916737499136, 2113929216, 1811939328, 913217421312, 112717121716224, 727326941773824}

vector <ll> nums = {1ll, 7ll, 49ll, 343ll, 5ll, 35ll, 1715ll, 175ll, 3ll, 21ll, 147ll, 15ll, 75ll, 9ll, 63ll, 441ll, 315ll, 1575ll, 77175ll, 27ll, 189ll, 1323ll, 135ll, 3375ll, 81ll, 1361367ll, 1121144263281ll, 243ll, 59535ll, 729ll, 2187ll, 321489ll, 137781ll, 413343ll, 177147ll, 1162261467ll, 2ll, 14ll, 98ll, 686ll, 33614ll, 6ll, 42ll, 294ll, 18ll, 126ll, 882ll, 6174ll, 43218ll, 2117682ll, 378ll, 2646ll, 162ll, 1134ll, 133413966ll, 486ll, 23814ll, 1166886ll, 71442ll, 214326ll, 13122ll, 642978ll, 3281116734ll, 4ll, 28ll, 1372ll, 67228ll, 12ll, 84ll, 4116ll, 1411788ll, 36ll, 1764ll, 12348ll, 324ll, 2268ll, 111132ll, 972ll, 8748ll, 61236ll, 236196ll, 8ll, 2744ll, 941192ll, 24ll, 168ll, 1176ll, 72ll, 216ll, 648ll, 1944ll, 666792ll, 122472ll, 1417176ll, 69441624ll, 16ll, 112ll, 784ll, 268912ll, 48ll, 144ll, 49392ll, 432ll, 148176ll, 3111696ll, 27216ll, 11664ll, 34992ll, 314928ll, 46294416ll, 32ll, 224ll, 184473632ll, 672ll, 32928ll, 288ll, 14112ll, 691488ll, 864ll, 42336ll, 18144ll, 2667168ll, 914838624ll, 23328ll, 163296ll, 13226976ll, 64ll, 448ll, 368947264ll, 192ll, 1344ll, 1382976ll, 1728ll, 4148928ll, 1778112ll, 139968ll, 2939328ll, 3779136ll, 3416267673274176ll, 128ll, 896ll, 6272ll, 131712ll, 19361664ll, 24192ll, 93312ll, 13716864ll, 1792ll, 1843968ll, 112896ll, 116169984ll, 7112448ll, 1229312ll, 3687936ll, 13824ll, 96768ll, 41472ll, 124416ll, 4444263936ll, 9483264ll, 1741824ll, 4182119424ll, 1792336896ll, 14336ll, 18432ll, 1161216ll, 1194891264ll, 1492992ll, 28672ll, 23612624896ll, 331776ll, 8192ll, 221184ll, 13884223438848ll, 11239424ll, 33718272ll, 71663616ll, 3211264ll, 9633792ll, 393216ll, 11329339392ll, 9437184ll, 1783627776ll, 169869312ll, 3699376128ll, 226492416ll, 128421199872ll, 1438916737499136ll, 2113929216ll, 1811939328ll, 913217421312ll, 112717121716224ll, 727326941773824ll};

vector <int> val = {1, 7, 8, 8, 5, 5, 5, 5, 3, 2, 6, 5, 5, 9, 8, 6, 5, 5, 5, 4, 4, 8, 5, 5, 8, 8, 8, 8, 5, 2, 2, 2, 8, 8, 8, 6, 2, 4, 4, 6, 2, 6, 8, 4, 8, 2, 6, 6, 8, 6, 6, 6, 2, 2, 6, 8, 8, 8, 6, 6, 2, 6, 6, 4, 6, 8, 6, 2, 6, 8, 2, 8, 6, 8, 8, 8, 6, 2, 2, 2, 6, 8, 6, 8, 8, 6, 8, 4, 2, 8, 6, 6, 6, 8, 6, 6, 2, 6, 2, 6, 6, 6, 8, 6, 2, 6, 6, 6, 2, 6, 6, 6, 6, 6, 8, 6, 8, 8, 8, 8, 6, 6, 6, 6, 6, 6, 8, 6, 2, 8, 6, 6, 2, 8, 6, 6, 6, 8, 6, 6, 8, 6, 8, 6, 6, 2, 6, 2, 6, 8, 2, 2, 2, 6, 8, 6, 6, 8, 6, 6, 2, 8, 6, 2, 8, 4, 8, 6, 6, 6, 6, 6, 6, 6, 2, 8, 6, 6, 2, 2, 6, 6, 8, 6, 6, 6, 4, 6, 6, 2, 6, 8, 8};

int N = 193;

//vector <vector <int> > ile(20, vector <int> (N, 0));

vector <ll> fac(19);

void prep_fac() {
	fac[0] = 1ll;
	for(ll i = 1ll; i < 19ll; ++i) fac[i] = fac[i - 1ll] * i;
}

ll binom(int l, vector <int> &a) {
	ll ans = fac[l];
	for(int &x : a) ans /= fac[x];
	return ans;
}

int a2, a3, a5, a7;

ll ile(int l, ll s) { // ile jest liczb dlugosci l dajacych w jednym ruchu s)
	if(l == 0) {
		if(s == 1ll) return 1ll;
		return 0ll;
	}

	ll sum = 0ll;
	for(int a4 = 0; a4 <= a2 / 2; ++a4) {
		for(int a8 = 0; a8 <= (a2 - 2 * a4) / 3; ++a8) {
			for(int a9 = 0; a9 <= a3 / 2; ++a9) {
				for(int a6 = 0; a6 <= min(a2 - 2 * a4 - 3 * a8, a3 - 2 * a9); ++a6) {
					int a22 = a2 - 2 * a4 - 3 * a8 - a6;
					int a33 = a3 - 2 * a9 - a6;
					int a1 = l - (a22 + a33 + a4 + a5 + a6 + a7 + a8 + a9);
					if(a1 >= 0) {
						vector <int> a = {a1, a22, a33, a4, a5, a6, a7, a8, a9};
						sum += binom(l, a);
					}
				}
			}
		}
	}
	return sum;
}

/*int log10(ll x) {
	while(x) {
		++len;
		x /= 10ll;
	}
	return len;
}*/

void solve() {
	ll nn; scanf("%lld", &nn);

	string n;
	//reverse(n.begin(), n.end());

	ll cpy = nn;
	while(nn) {
		n += (char) ((nn % 10ll) + '0');
		nn /= 10ll;
	}
	nn = cpy;

	/*for(char c : n) printf("%c", c);
	printf("\n");*/

	int len = (int) n.length();
	
	vector <ll> ans(10, 0ll);

	for(int i = 0; i < N; ++i) {

		a2 = 0, a3 = 0, a5 = 0, a7 = 0;
		ll x = nums[i];
		while((x % 2ll) == 0) ++a2, x /= 2ll;
		while((x % 3ll) == 0) ++a3, x /= 3ll;
		while((x % 5ll) == 0) ++a5, x /= 5ll;
		while((x % 7ll) == 0) ++a7, x /= 7ll;
		x = nums[i];

		//printf("%lld %d %d %d %d\n", x, a2, a3, a5, a7);

		int v = val[i];
		for(int l = len; l; --l) {
			int c = n[l - 1] - '0';
			if(c == 0) continue;
			for(int d = 1; d < (ll)c; ++d) {
				if((x % d) == 0) ans[v] += ile(l - 1, x / ((ll)d));
			}
			/*if(c > 1) ans[v] += ile(l - 1, x); // 1 na poczatku
			if(a2 && c > 2) ans[v] += ile(l - 1, x / 2ll); // 2
			if(a3 && c > 3) ans[v] += ile(l - 1, x / 3ll); // 3
			if(a5 && c > 5) ans[v] += ile(l - 1, x / 5ll); // 5
			if(a7 && c > 7) ans[v] += ile(l - 1, x / 7ll); // 7*/
			if(x % c) break;
			x /= c;
			if(x == 1 && l == 1) ++ans[v];
			/*if(c == 1) {
				//if(l == 1 && x == 1) ++ans[v];
				continue;
			}
			else if(c == 2) x /= 2ll;
			else if(c == 3) x /= 3ll;
			else if(c == 5) x /= 5ll;
			else if(c == 7) x /= 7ll;
			else break;*/
		}

		for(int l = len - 1; l > 0; --l) {
			ans[v] += ile(l, x);
		}
	}

	ll sum = 0ll;
	for(int i = 1; i < 10; ++i) sum += ans[i];
	ans[0] = nn - sum;

	for(int i = 0; i < 10; ++i) printf("%lld ", ans[i]);
	printf("\n");
}

int main() {
	prep_fac();
	int t; scanf("%d", &t);
	for(++t; --t;) solve();
	return 0;
}