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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
/*vector<pair<LL, int>> num;
vector<vector<int>> representations;
vector<int> wynik;*/
LL num[][2]={{1, 0}, {2, 36}, {3, 8}, {4, 63}, {5, 4}, {6, 41}, {7, 1}, {8, 81}, {9, 13}, {12, 67}, {14, 37}, {15, 11}, {16, 95}, {18, 44}, {21, 9}, {24, 84}, {27, 19}, {28, 64}, {32, 110}, {35, 5}, {36, 71}, {42, 42}, {48, 99}, {49, 2}, {63, 14}, {64, 126}, {72, 87}, {75, 12}, {81, 24}, {84, 68}, {98, 38}, {112, 96}, {126, 45}, {128, 139}, {135, 22}, {144, 100}, {147, 10}, {162, 52}, {168, 85}, {175, 7}, {189, 20}, {192, 129}, {216, 88}, {224, 111}, {243, 27}, {288, 115}, {294, 43}, {315, 16}, {324, 74}, {343, 3}, {378, 50}, {432, 102}, {441, 15}, {448, 127}, {486, 55}, {648, 89}, {672, 113}, {686, 39}, {729, 29}, {784, 97}, {864, 118}, {882, 46}, {896, 140}, {972, 77}, {1134, 53}, {1176, 86}, {1323, 21}, {1344, 130}, {1372, 65}, {1575, 17}, {1715, 6}, {1728, 132}, {1764, 72}, {1792, 147}, {1944, 90}, {2187, 30}, {2268, 75}, {2646, 51}, {2744, 82}, {3375, 23}, {4116, 69}, {6174, 47}, {6272, 141}, {8192, 171}, {8748, 78}, {11664, 106}, {12348, 73}, {13122, 60}, {13824, 154}, {14112, 116}, {14336, 163}, {18144, 120}, {18432, 164}, {23328, 123}, {23814, 56}, {24192, 144}, {27216, 105}, {28672, 168}, {32928, 114}, {33614, 40}, {34992, 107}, {41472, 156}, {42336, 119}, {43218, 48}, {49392, 101}, {59535, 28}, {61236, 79}, {67228, 66}, {71442, 58}, {77175, 18}, {93312, 145}, {96768, 155}, {111132, 76}, {112896, 149}, {122472, 92}, {124416, 157}, {131712, 142}, {137781, 32}, {139968, 135}, {148176, 103}, {163296, 124}, {177147, 34}, {214326, 59}, {221184, 172}, {236196, 80}, {268912, 98}, {314928, 108}, {321489, 31}, {331776, 170}, {393216, 179}, {413343, 33}, {642978, 61}, {666792, 91}, {691488, 117}, {941192, 83}, {1161216, 165}, {1166886, 57}, {1229312, 152}, {1361367, 25}, {1382976, 131}, {1411788, 70}, {1417176, 93}, {1492992, 167}, {1741824, 160}, {1778112, 134}, {1843968, 148}, {2117682, 49}, {2667168, 121}, {2939328, 136}, {3111696, 104}, {3211264, 177}, {3687936, 153}, {3779136, 137}, {4148928, 133}, {7112448, 151}, {9437184, 181}, {9483264, 159}, {9633792, 178}, {11239424, 174}, {13226976, 125}, {13716864, 146}, {19361664, 143}, {33718272, 175}, {46294416, 109}, {69441624, 94}, {71663616, 176}, {116169984, 150}, {133413966, 54}, {169869312, 183}, {184473632, 112}, {226492416, 185}, {368947264, 128}, {914838624, 122}, {1162261467, 35}, {1194891264, 166}, {1783627776, 182}, {1792336896, 162}, {1811939328, 189}, {2113929216, 188}, {3281116734, 62}, {3699376128, 184}, {4182119424, 161}, {4444263936, 158}, {11329339392, 180}, {23612624896, 169}, {128421199872, 186}, {913217421312, 190}, {1121144263281, 26}, {13884223438848, 173}, {112717121716224, 191}, {727326941773824, 192}, {1438916737499136, 187}, {3416267673274176, 138}};
int representations[][4]={{0, 0, 0, 0}, {0, 0, 0, 1}, {0, 0, 0, 2}, {0, 0, 0, 3}, {0, 0, 1, 0}, {0, 0, 1, 1}, {0, 0, 1, 3}, {0, 0, 2, 1}, {0, 1, 0, 0}, {0, 1, 0, 1}, {0, 1, 0, 2}, {0, 1, 1, 0}, {0, 1, 2, 0}, {0, 2, 0, 0}, {0, 2, 0, 1}, {0, 2, 0, 2}, {0, 2, 1, 1}, {0, 2, 2, 1}, {0, 2, 2, 3}, {0, 3, 0, 0}, {0, 3, 0, 1}, {0, 3, 0, 2}, {0, 3, 1, 0}, {0, 3, 3, 0}, {0, 4, 0, 0}, {0, 4, 0, 5}, {0, 4, 0, 12}, {0, 5, 0, 0}, {0, 5, 1, 2}, {0, 6, 0, 0}, {0, 7, 0, 0}, {0, 8, 0, 2}, {0, 9, 0, 1}, {0, 10, 0, 1}, {0, 11, 0, 0}, {0, 19, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 1}, {1, 0, 0, 2}, {1, 0, 0, 3}, {1, 0, 0, 5}, {1, 1, 0, 0}, {1, 1, 0, 1}, {1, 1, 0, 2}, {1, 2, 0, 0}, {1, 2, 0, 1}, {1, 2, 0, 2}, {1, 2, 0, 3}, {1, 2, 0, 4}, {1, 2, 0, 6}, {1, 3, 0, 1}, {1, 3, 0, 2}, {1, 4, 0, 0}, {1, 4, 0, 1}, {1, 4, 0, 7}, {1, 5, 0, 0}, {1, 5, 0, 2}, {1, 5, 0, 4}, {1, 6, 0, 2}, {1, 7, 0, 2}, {1, 8, 0, 0}, {1, 8, 0, 2}, {1, 14, 0, 3}, {2, 0, 0, 0}, {2, 0, 0, 1}, {2, 0, 0, 3}, {2, 0, 0, 5}, {2, 1, 0, 0}, {2, 1, 0, 1}, {2, 1, 0, 3}, {2, 1, 0, 6}, {2, 2, 0, 0}, {2, 2, 0, 2}, {2, 2, 0, 3}, {2, 4, 0, 0}, {2, 4, 0, 1}, {2, 4, 0, 3}, {2, 5, 0, 0}, {2, 7, 0, 0}, {2, 7, 0, 1}, {2, 10, 0, 0}, {3, 0, 0, 0}, {3, 0, 0, 3}, {3, 0, 0, 6}, {3, 1, 0, 0}, {3, 1, 0, 1}, {3, 1, 0, 2}, {3, 2, 0, 0}, {3, 3, 0, 0}, {3, 4, 0, 0}, {3, 5, 0, 0}, {3, 5, 0, 3}, {3, 7, 0, 1}, {3, 11, 0, 0}, {3, 11, 0, 2}, {4, 0, 0, 0}, {4, 0, 0, 1}, {4, 0, 0, 2}, {4, 0, 0, 5}, {4, 1, 0, 0}, {4, 2, 0, 0}, {4, 2, 0, 3}, {4, 3, 0, 0}, {4, 3, 0, 3}, {4, 4, 0, 4}, {4, 5, 0, 1}, {4, 6, 0, 0}, {4, 7, 0, 0}, {4, 9, 0, 0}, {4, 10, 0, 2}, {5, 0, 0, 0}, {5, 0, 0, 1}, {5, 0, 0, 8}, {5, 1, 0, 1}, {5, 1, 0, 3}, {5, 2, 0, 0}, {5, 2, 0, 2}, {5, 2, 0, 4}, {5, 3, 0, 0}, {5, 3, 0, 2}, {5, 4, 0, 1}, {5, 5, 0, 3}, {5, 5, 0, 6}, {5, 6, 0, 0}, {5, 6, 0, 1}, {5, 10, 0, 1}, {6, 0, 0, 0}, {6, 0, 0, 1}, {6, 0, 0, 8}, {6, 1, 0, 0}, {6, 1, 0, 1}, {6, 2, 0, 4}, {6, 3, 0, 0}, {6, 3, 0, 4}, {6, 4, 0, 3}, {6, 7, 0, 0}, {6, 8, 0, 1}, {6, 10, 0, 0}, {6, 27, 0, 1}, {7, 0, 0, 0}, {7, 0, 0, 1}, {7, 0, 0, 2}, {7, 1, 0, 3}, {7, 2, 0, 5}, {7, 3, 0, 1}, {7, 6, 0, 0}, {7, 7, 0, 2}, {8, 0, 0, 1}, {8, 1, 0, 4}, {8, 2, 0, 2}, {8, 3, 0, 5}, {8, 4, 0, 3}, {9, 0, 0, 4}, {9, 1, 0, 4}, {9, 3, 0, 0}, {9, 3, 0, 1}, {9, 4, 0, 0}, {9, 5, 0, 0}, {9, 11, 0, 2}, {10, 3, 0, 3}, {10, 5, 0, 1}, {10, 5, 0, 5}, {10, 6, 0, 4}, {11, 0, 0, 1}, {11, 2, 0, 0}, {11, 4, 0, 1}, {11, 5, 0, 4}, {11, 6, 0, 0}, {12, 0, 0, 1}, {12, 0, 0, 8}, {12, 4, 0, 0}, {13, 0, 0, 0}, {13, 3, 0, 0}, {14, 1, 0, 10}, {15, 0, 0, 3}, {15, 1, 0, 3}, {15, 7, 0, 0}, {16, 0, 0, 2}, {16, 1, 0, 2}, {17, 1, 0, 0}, {19, 2, 0, 4}, {20, 2, 0, 0}, {20, 5, 0, 1}, {21, 4, 0, 0}, {23, 2, 0, 2}, {23, 3, 0, 0}, {23, 7, 0, 1}, {24, 6, 0, 6}, {25, 2, 0, 1}, {26, 3, 0, 0}, {29, 5, 0, 1}, {34, 8, 0, 0}, {39, 3, 0, 2}};
int representations_copy[][4]={{0, 0, 0, 0}, {0, 0, 0, 1}, {0, 0, 0, 2}, {0, 0, 0, 3}, {0, 0, 1, 0}, {0, 0, 1, 1}, {0, 0, 1, 3}, {0, 0, 2, 1}, {0, 1, 0, 0}, {0, 1, 0, 1}, {0, 1, 0, 2}, {0, 1, 1, 0}, {0, 1, 2, 0}, {0, 2, 0, 0}, {0, 2, 0, 1}, {0, 2, 0, 2}, {0, 2, 1, 1}, {0, 2, 2, 1}, {0, 2, 2, 3}, {0, 3, 0, 0}, {0, 3, 0, 1}, {0, 3, 0, 2}, {0, 3, 1, 0}, {0, 3, 3, 0}, {0, 4, 0, 0}, {0, 4, 0, 5}, {0, 4, 0, 12}, {0, 5, 0, 0}, {0, 5, 1, 2}, {0, 6, 0, 0}, {0, 7, 0, 0}, {0, 8, 0, 2}, {0, 9, 0, 1}, {0, 10, 0, 1}, {0, 11, 0, 0}, {0, 19, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 1}, {1, 0, 0, 2}, {1, 0, 0, 3}, {1, 0, 0, 5}, {1, 1, 0, 0}, {1, 1, 0, 1}, {1, 1, 0, 2}, {1, 2, 0, 0}, {1, 2, 0, 1}, {1, 2, 0, 2}, {1, 2, 0, 3}, {1, 2, 0, 4}, {1, 2, 0, 6}, {1, 3, 0, 1}, {1, 3, 0, 2}, {1, 4, 0, 0}, {1, 4, 0, 1}, {1, 4, 0, 7}, {1, 5, 0, 0}, {1, 5, 0, 2}, {1, 5, 0, 4}, {1, 6, 0, 2}, {1, 7, 0, 2}, {1, 8, 0, 0}, {1, 8, 0, 2}, {1, 14, 0, 3}, {2, 0, 0, 0}, {2, 0, 0, 1}, {2, 0, 0, 3}, {2, 0, 0, 5}, {2, 1, 0, 0}, {2, 1, 0, 1}, {2, 1, 0, 3}, {2, 1, 0, 6}, {2, 2, 0, 0}, {2, 2, 0, 2}, {2, 2, 0, 3}, {2, 4, 0, 0}, {2, 4, 0, 1}, {2, 4, 0, 3}, {2, 5, 0, 0}, {2, 7, 0, 0}, {2, 7, 0, 1}, {2, 10, 0, 0}, {3, 0, 0, 0}, {3, 0, 0, 3}, {3, 0, 0, 6}, {3, 1, 0, 0}, {3, 1, 0, 1}, {3, 1, 0, 2}, {3, 2, 0, 0}, {3, 3, 0, 0}, {3, 4, 0, 0}, {3, 5, 0, 0}, {3, 5, 0, 3}, {3, 7, 0, 1}, {3, 11, 0, 0}, {3, 11, 0, 2}, {4, 0, 0, 0}, {4, 0, 0, 1}, {4, 0, 0, 2}, {4, 0, 0, 5}, {4, 1, 0, 0}, {4, 2, 0, 0}, {4, 2, 0, 3}, {4, 3, 0, 0}, {4, 3, 0, 3}, {4, 4, 0, 4}, {4, 5, 0, 1}, {4, 6, 0, 0}, {4, 7, 0, 0}, {4, 9, 0, 0}, {4, 10, 0, 2}, {5, 0, 0, 0}, {5, 0, 0, 1}, {5, 0, 0, 8}, {5, 1, 0, 1}, {5, 1, 0, 3}, {5, 2, 0, 0}, {5, 2, 0, 2}, {5, 2, 0, 4}, {5, 3, 0, 0}, {5, 3, 0, 2}, {5, 4, 0, 1}, {5, 5, 0, 3}, {5, 5, 0, 6}, {5, 6, 0, 0}, {5, 6, 0, 1}, {5, 10, 0, 1}, {6, 0, 0, 0}, {6, 0, 0, 1}, {6, 0, 0, 8}, {6, 1, 0, 0}, {6, 1, 0, 1}, {6, 2, 0, 4}, {6, 3, 0, 0}, {6, 3, 0, 4}, {6, 4, 0, 3}, {6, 7, 0, 0}, {6, 8, 0, 1}, {6, 10, 0, 0}, {6, 27, 0, 1}, {7, 0, 0, 0}, {7, 0, 0, 1}, {7, 0, 0, 2}, {7, 1, 0, 3}, {7, 2, 0, 5}, {7, 3, 0, 1}, {7, 6, 0, 0}, {7, 7, 0, 2}, {8, 0, 0, 1}, {8, 1, 0, 4}, {8, 2, 0, 2}, {8, 3, 0, 5}, {8, 4, 0, 3}, {9, 0, 0, 4}, {9, 1, 0, 4}, {9, 3, 0, 0}, {9, 3, 0, 1}, {9, 4, 0, 0}, {9, 5, 0, 0}, {9, 11, 0, 2}, {10, 3, 0, 3}, {10, 5, 0, 1}, {10, 5, 0, 5}, {10, 6, 0, 4}, {11, 0, 0, 1}, {11, 2, 0, 0}, {11, 4, 0, 1}, {11, 5, 0, 4}, {11, 6, 0, 0}, {12, 0, 0, 1}, {12, 0, 0, 8}, {12, 4, 0, 0}, {13, 0, 0, 0}, {13, 3, 0, 0}, {14, 1, 0, 10}, {15, 0, 0, 3}, {15, 1, 0, 3}, {15, 7, 0, 0}, {16, 0, 0, 2}, {16, 1, 0, 2}, {17, 1, 0, 0}, {19, 2, 0, 4}, {20, 2, 0, 0}, {20, 5, 0, 1}, {21, 4, 0, 0}, {23, 2, 0, 2}, {23, 3, 0, 0}, {23, 7, 0, 1}, {24, 6, 0, 6}, {25, 2, 0, 1}, {26, 3, 0, 0}, {29, 5, 0, 1}, {34, 8, 0, 0}, {39, 3, 0, 2}};

int wynik[]={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 t1[]={2, 3, 5, 7};
int t2[]={3, 2, 1, 1};

vector<int> rep;

int ile_cyfr[9];
vector<int> N;
LL silnia[19];
LL ile_liczb(int i, bool freee, int sum){
	if(i==N.size()) return 1;
	if(sum==0) return 0;
	if(freee){
		LL wyn=silnia[sum];
		for(int j=0; j<9; j++) wyn/=silnia[ile_cyfr[j]];
		return wyn;
	}
	LL wyn=0;
	for(int j=0; j<N[i]; j++){
		if(ile_cyfr[j]!=0){
			ile_cyfr[j]--;
			wyn+=ile_liczb(i+1, (j!=N[i]-1), sum-1);
			ile_cyfr[j]++;
		}
	}
	return wyn;
}
LL WYNIK[10];
void gener(LL nn, int i, int s, int j){
	if(s>N.size()) return;
	if(i==0){
		for(; representations_copy[j][0]>=0 && representations_copy[j][1]>=0; representations_copy[j][0]--, representations_copy[j][1]--){
			gener(nn, i+1, s+1, j);
		}
	}
	
}
void gen_cyfry(LL nn){
	for(int iii=0; iii<193 && num[iii][0]<=nn; iii++){
		int i=num[iii][1];
		//cout<<"Liczba: "<<num[iii].first<<'\n';
		for(int u=0; u<=min(representations[i][0], representations[i][1]); u++){ //6
		    representations[i][0]-=u; representations[i][1]-=u;
			for(int j=0; j<=representations[i][0]/3; j++){//8
			    representations[i][0]-=j*3;
				for(int k=0; k<=representations[i][0]/2; k++){//4
				    representations[i][0]-=k*2;
					for(int o=0; o<=representations[i][1]/2; o++){//9
						int l=representations[i][0];//2
						int p=(representations[i][1]-o*2);//3
						int r=representations[i][2];//5
						int s=representations[i][3];//7
						for(int t=0; t+l+p+k+r+u+s+j+o<=N.size(); t++){//1
							ile_cyfr[0]=t; ile_cyfr[1]=l; ile_cyfr[2]=p; ile_cyfr[3]=k; ile_cyfr[4]=r; ile_cyfr[5]=u; ile_cyfr[6]=s; ile_cyfr[7]=j; ile_cyfr[8]=o;
							//for(int iiii=0; iiii<ile_cyfr.size(); iiii++) cout<<ile_cyfr[iiii]<<' '; cout<<'\n';
							WYNIK[wynik[i]]+=ile_liczb(0, (t+l+p+k+r+u+s+j+o<N.size()), t+l+p+k+r+u+s+j+o);
						}
					}
					representations[i][0]+=k*2;
				}
				representations[i][0]+=j*3;
			}
			representations[i][0]+=u; representations[i][1]+=u;
		}
	}
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	LL t=(cin>>t, t), nn;
	silnia[0]=1;
	for(int i=1; i<19; i++) silnia[i]=i*silnia[i-1];
	while(t--){
		cin>>nn;
		N.clear();
		for(int i=0; i<193; i++) for(int j=0; j<4; j++) 
		for(int i=0; i<10; i++) WYNIK[i]=0;
		for(LL x=nn; x>0; x/=10) N.emplace_back(x%10);
		reverse(N.begin(), N.end());
		gen_cyfry(nn);
		LL sssss=0;
		for(int i=1; i<10; i++) sssss+=WYNIK[i];
		WYNIK[0]=nn-sssss;
		for(int i=0; i<10; i++) cout<<WYNIK[i]<<' '; cout<<'\n';
	}
	
    return 0;
}