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
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)

using namespace std;

typedef long long llint;

const llint M18 = 1000000000000000000;

int t;
llint n, p;

llint C[10];

struct hash_pair_llint {
    std::size_t operator () (const std::pair<llint,llint> &p) const {
        return std::hash<llint>{}(p.first) ^ std::hash<llint>{}(p.second);
    }
};

unordered_map<pair<llint, llint>, llint, hash_pair_llint> qmap;

vector<pair<llint, char>> vv;

llint calc_q(llint n, llint g, llint tk) {
	auto it = qmap.find(make_pair(n,g));
	if (it != qmap.end()) return it->second;
	llint res = 0;
	if (n > 9) {
		FOR(b, 1, 9) {
			if (g % b) continue;
			llint btk = b*tk;
			if (btk > n) break;
			if (btk <= g) continue;			
			llint tk10=tk/10, n1 = n-btk;
			if (n1 >= tk) {
				res += calc_q(tk - 1, g/b, tk/10);
			} else if (n1 >= tk/10) {
				res += calc_q(n1, g/b, tk/10);
			}
		}
	} else {
		res = (g <= n);
	}
	qmap[make_pair(n,g)] = res;
	return res;
}

inline llint compute_q(llint n, llint g) {
	llint res = 0, tk = 1, n1 = n;
	while (n1 > 9) { 
		n1 /= 10; tk *= 10; 
		if (g < tk) 
			res += calc_q(tk-1, g, tk/10); 
	}	
	res += calc_q(n, g, tk);
	return res;
}

int main(void) {	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
		
	llint f2 = 1;
	REP(a2, 60) { llint f3 = 1;
		REP(a3, 38) { llint f5 = 1;
			REP(a5, 26) { llint f7 = 1;
				REP(a7, 22) {
					if (f2 < M18 / f3 && f2*f3 < M18 / f5 && f2*f3*f5 < M18 / f7) {
						n = p = f2*f3*f5*f7;
						for(;;) {
							if (p < 10) break;
							llint q = 1;
							while (p > 9) { q *= p % 10; p /= 10; }
							p *= q;
						}
						if (p) vv.push_back(make_pair(n, p));
					}					
					f7 *= 7;
				}
				f5 *= 5;
			}
			f3 *= 3;
		}
		f2 *= 2;
	}

	qmap.clear();

	cin >> t;
	REP(i, t) { 
		cin >> n;
		REP(i, 10) C[i] = 0;
		
		int vv_s = vv.size();
		REP(vvix, vv_s) {
			llint g = vv[vvix].first;
			char d = vv[vvix].second;
			C[d] += compute_q(n, g);
		}
		
		C[0] = n;
		FOR(i, 1, 9) C[0] -= C[i];
		REP(i, 9) cout << C[i] << " "; cout << C[9] << endl;
	}
	
	return 0;
}