#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000050;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
long long C(long long m, long long n) {
  if (m < n) return 0;
  n = max(n, m - n);
  long long ans = 1;
  for (long long i = n + 1; i <= m; i++) ans *= i;
  for (long long i = 2; i <= m - n; i++) ans /= i;
  return ans;
}
int a[52];
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    long long i, j, k, m, n;
    memset(a, 0, sizeof a);
    cin >> n;
    k = 2;
    while (n) {
      a[n % k]++;
      n /= k;
      k++;
    }
    k--;
    long long ans = 1, ans2 = 1, x = 0;
    for (i = k; i >= 1; i--) {
      if (a[i]) {
        ans *= C(k - i - x, a[i]);
        if (a[0]) ans2 *= C(k - i - 1 - x, a[i]);
        x += a[i];
      }
    }
    if (a[0]) ans -= ans2;
    cout << ans - 1 << endl;
  }
  return 0;
}
