#include <bits/stdc++.h>
using namespace std;
const long long int N = 1e5, mod = 1e9 + 7;
long long int fac[20];
long long int ncr(long long int n, long long int r) {
  if (n == 0 || r > n) {
    return 0;
  }
  long long int z = fac[n];
  z = z / fac[r];
  z = z / fac[n - r];
  return z;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  fac[0] = 1;
  for (long long int i = 1; i < (long long int)20; i++) {
    fac[i] = i * fac[i - 1];
  }
  long long int t;
  cin >> t;
  while (t--) {
    long long int n;
    cin >> n;
    vector<long long int> v;
    long long int c = 2;
    while (n) {
      v.push_back(n % c);
      n /= c;
      c++;
    }
    sort(v.begin(), v.end());
    long long int f = 0;
    if (v[0] == 0) f = 1;
    long long int ans = 1;
    n = (long long int)v.size();
    long long int filled = 0;
    for (long long int i = n - 1; i >= (long long int)0; i--) {
      long long int cur = v[i];
      long long int cnt = 0;
      while (i >= 0 && v[i] == cur) {
        i--;
        cnt++;
      }
      i++;
      long long int tot = n - max(cur, (long long int)1) + 1;
      long long int rem = tot - filled;
      ans *= ncr(rem, cnt);
      filled += cnt;
    }
    long long int ans2 = 1;
    if (f == 1) {
      filled = 1;
      for (long long int i = n - 1; i >= (long long int)0; i--) {
        long long int cur = v[i];
        long long int cnt = 0;
        while (i >= 0 && v[i] == cur) {
          i--;
          cnt++;
        }
        i++;
        if (i == 0) {
          break;
        }
        long long int tot = n - max(cur, (long long int)1) + 1;
        long long int rem = tot - filled;
        ans2 *= ncr(rem, cnt);
        filled += cnt;
      }
    } else {
      ans2 = 0;
    }
    cout << ans - ans2 - 1 << "\n";
  }
}
