#include<bits/stdc++.h>
using namespace std;

#define QwQ330AwA return 0
#define ll __int128

void write(ll x) {
	vector <int> stk;
	while (x) stk.push_back(x % 10), x /= 10;
	reverse(stk.begin(), stk.end());
	for (auto w : stk) cout << w;
}

ll fac[33];
ll pw[33][33];
vector < pair <ll, ll> > pos[33];
ll c[33][33];
ll lim;
int id;

void dfs(int now, int cnt, ll ans, ll sum) {
//	cout << now << ' ' << cnt << ' ';
//	write(ans), cout << ' ';
//	write(sum), cout << '\n';
	if (sum < lim / pw[9][cnt]) return ;
	if (now == 9) {
		pos[id].push_back({sum * pw[9][cnt], ans});
		return ;
	}
	for (int i = 0; i <= cnt; i++) {
		dfs(now + 1, cnt - i, ans * c[cnt][i], sum * pw[now][i]);
	}
}

void init() {
	fac[0] = 1;
	for (int i = 1; i <= 21; i++) fac[i] = fac[i - 1] * i;
	for (int i = 1; i <= 10; i++) {
		pw[i][0] = 1;
		for (int j = 1; j < 33; j++) pw[i][j] = pw[i][j - 1] * i;
	}
	for (int i = 0; i <= 21; i++) {
		c[i][0] = c[i][i] = 1;
		for (int j = 1; j < i; j++) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
	}
}

int num[33];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	init();
	ll Ans = 0;
	for (int i = 1; i <= 21; i++) {
		lim = fac[i];
		for (int j = i + 1; j <= 21; j++) lim = min(lim, (fac[j] - 1) / pw[9][j - i] + 1);
		id = i;
		dfs(1, i, 1, 1);
		sort(pos[i].begin(), pos[i].end());
		//assert(pos[i].begin() -> first >= fac[i]);
//		cout << i << endl;
//		for (auto x : pos[i]) write(x.first), cout << ' ';
//		cout << endl;
		//cout << pos[i].size() << endl;
		reverse(pos[i].begin(), pos[i].end());
		vector < pair <ll, ll> > sp;
		for (int j = 0, k = 0; j < (int)pos[i].size(); j = k) {
			ll sum = 0;
			while (k < (int)pos[i].size() && pos[i][j].first == pos[i][k].first) sum += pos[i][k].second, k++;
			sp.push_back({pos[i][j].first, sum});
		}
		pos[i] = sp;
		for (int j = 1; j < (int)pos[i].size(); j++) pos[i][j].second += pos[i][j - 1].second;
		int l = 0, r = pos[i].size() - 1, ans = -1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (pos[i][mid].first >= fac[i]) ans = mid, l = mid + 1;
			else r = mid - 1;
		}
		if (ans != -1) Ans += pos[i][ans].second;		
	}
	int t;
	cin >> t;
	while (t--) {
		string s;
		cin >> s;
		if (s.length() > 21) {
			write(Ans);
			cout << '\n';
			continue;
		}
		reverse(s.begin(), s.end());
		for (int i = 0; i < (int)s.length(); i++) num[i] = s[i] - '0';
		int len = s.length();
		ll sum = 0;
		for (int i = 1; i < len; i++) {
			int l = 0, r = pos[i].size() - 1, ans = -1;
			while (l <= r) {
				int mid = (l + r) / 2;
				if (pos[i][mid].first >= fac[i]) ans = mid, l = mid + 1;
				else r = mid - 1;
			}
			if (ans != -1) sum += pos[i][ans].second;
		}
		ll pre = 1;
		for (int i = len - 1; i >= 0; i--) {
			for (int x = 1; x < num[i]; x++) {
				if (i == 0) {
					sum += (pre * x >= fac[len]);
					continue;
				}
				int l = 0, r = pos[i].size() - 1, ans = -1;
				while (l <= r) {
					int mid = (l + r) / 2;
					ll p = pos[i][mid].first;
					p *= x;
					if (p >= fac[len]) {
						ans = mid;
						l = mid + 1;
					} else {
						p *= pre;
						if (p >= fac[len]) ans = mid, l = mid + 1;
						else r = mid - 1;
					}
				}
				if (ans != -1) sum += pos[i][ans].second;
			}
			pre *= num[i];
			if (pre == 0) break;
		}
		if (pre >= fac[len]) sum++;
		write(sum);
		cout << '\n';
	}
	QwQ330AwA;
}