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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <iostream>
#include <array>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

const unsigned long long MAXN = 1000000000000000000LL;
const int MAXCYFR = 18;


unsigned long long dziel_do_skutku(unsigned long long a) {
	unsigned long long res = 1;
	while(a > 0) {
		res *= a % 10;
		a /= 10;
	}
	if(res < 10)
		return res;
	else
		return dziel_do_skutku(res);
}



array< vector< pair<unsigned long long, array<int,4> > >, 10 > zlozone; // z dzielnikami 2,3,5,7


void precompute_zlozone() {
	int i2 = 0;
	for(unsigned long long w2 = 1; w2 < MAXN; w2 *= 2) {
		int i3 = 0;
		for(unsigned long long w3 = w2; w3 < MAXN; w3 *= 3) {
			int i5 = 0;
			for(unsigned long long w5 = w3; w5 < MAXN; w5 *= 5) {				
				int i7 = 0;
				for(unsigned long long w7 = w5; w7 < MAXN ; w7 *= 7) {
					zlozone[dziel_do_skutku(w7)].push_back( pair<unsigned long long, array<int,4> >(w7, array<int,4>({i2,i3,i5,i7}) ) );
					i7++;
				}
				i5++;
			}
			i3++;
		}
		i2++;
	}
	for(int i =0; i< 10; i++) {
		sort(zlozone[i].begin(), zlozone[i].end());
	}
}


int ile_cyfr(unsigned long long n) {
	int res = 0;
	while(n > 0) {
		n /= 10;
		res++;
	}
	return res;
}


unsigned long long factorial(int n) {
	unsigned long long 	res = 1;
	for(int i = 2; i <= n; i++)
		res *= i;
	return res;
}


unsigned long long wylicz2(array<int,10> litery, unsigned long long n) {
	if(accumulate(litery.begin()+1, litery.begin()+10, 0) == 0)
		return 1;

	// przypadek dla tej samej liczby liter
	unsigned long long rzad = 1;
	int potega = ile_cyfr(n)-1;
	for(int i = 0; i < potega; i++)
		rzad *= 10;
	
	int pierwsza_cyfra = n / rzad;
	unsigned long long reszta = n % rzad;
	
	unsigned long long res = 0;
	
	for(int i = 1; i < pierwsza_cyfra; i++) {
		if(litery[i] == 0)
			continue;
		litery[i]--;
		res += factorial(potega) / (factorial(litery[1]) * factorial(litery[2])* factorial(litery[3])* factorial(litery[4])* factorial(litery[5])* factorial(litery[6])* factorial(litery[7])* factorial(litery[8])* factorial(litery[9])) ;
		litery[i]++;
	}
	if(litery[pierwsza_cyfra]>0) {
		litery[pierwsza_cyfra]--;
		res+=wylicz2(litery, reszta);
		litery[pierwsza_cyfra]++;
	}
	return res;
}


unsigned long long wylicz(array<int,4> dziel, unsigned long long n) {
	unsigned long long res = 0;
	int n_cyfr = ile_cyfr(n);
	
	array<int, 10> litery = array<int, 10>();
	litery[1] = 0;
	litery[5] = dziel[2];
	litery[7] = dziel[3];
	for(int szostek = 0; szostek <= dziel[0] && szostek <= dziel[1]; szostek++) {
	litery[6] = szostek;
	for(int czworek = 0; 2*czworek+szostek <= dziel[0]; czworek++)
		for(int osemek = 0; 2*czworek + 3*osemek+szostek <= dziel[0]; osemek++) {
			litery[2] = dziel[0]-2*czworek-3*osemek-szostek;
			litery[4] = czworek;
			litery[8] = osemek;
			
			for(int dziewiatek = 0; 2*dziewiatek+szostek <= dziel[1]; dziewiatek++) {
				litery[9] = dziewiatek;
				litery[3] = dziel[1] - 2*dziewiatek-szostek;
				
				int dotad_cyfr = accumulate(litery.begin()+2, litery.begin()+10, 0);
				if(dotad_cyfr > n_cyfr)
					continue;
				
				for(litery[1] = dotad_cyfr>0 ? 0 : 1; dotad_cyfr + litery[1]< n_cyfr; litery[1]++) {
					res += factorial(dotad_cyfr + litery[1]) / (factorial(litery[1]) * factorial(litery[2])* factorial(litery[3])* factorial(litery[4])* factorial(litery[5])* factorial(litery[6])* factorial(litery[7])* factorial(litery[8])* factorial(litery[9])) ;
				}
				
				res += wylicz2(litery, n);
			}
				
		}
	}
			
	return res;
}



void zrob_przypadek() {
    unsigned long long n;
	cin >> n;
	
	unsigned long long krotnosci[10];
	for(int i = 1; i < 10; i++) {
	  krotnosci[i] = 0;
	  for(int j = 0; j < zlozone[i].size(); j++)
		  krotnosci[i] += wylicz(zlozone[i][j].second, n);
	}
  
  
    krotnosci[0] = n;
	for(int i = 1; i < 10; i++)
		krotnosci[0] -= krotnosci[i];
	
	
	for(int i = 0; i < 10; i++)
		cout << krotnosci[i] << " ";
	cout << endl;
}


int main() {
  precompute_zlozone();
  int t = 1; 
  cin >> t;
  for(int i = 0; i < t; i++)
    zrob_przypadek();
  return 0;
}