#include <bits/stdc++.h>
using namespace std;
vector<long long> f(21);
long long fact(long long x) { return f[x]; }
long long solve(long long k) {
  vector<long long> cnt(21), less(21);
  long long d = 1, den = 1, num = 1, den1 = 1, num1 = 0;
  while (k > 0) {
    d += 1;
    cnt[k % d] += 1;
    k /= d;
  }
  less[d + 1] = d - 1;
  den = fact(cnt[0]) * fact(cnt[1]);
  for (long long i = d; i > 1LL; i--) {
    den *= fact(cnt[i]);
    less[i] = less[i + 1] - cnt[i];
    num *= (less[i] - (i - 2LL));
    if (num % den == 0) {
      num /= den;
      den = 1;
    }
  }
  if (cnt[0] > 0) {
    num1 = 1;
    cnt[0]--;
    less[d] -= 1;
    den1 = fact(cnt[0]) * fact(cnt[1]);
    for (long long i = d - 1; i > 1; i--) {
      den1 *= fact(cnt[i]);
      less[i] = less[i + 1] - cnt[i];
      num1 *= (less[i] - (i - 2LL));
      if (num1 % den1 == 0) {
        num1 /= den1;
        den1 = 1;
      }
    }
  }
  long long res = (num / den) - (num1 / den1) - 1LL;
  return res;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  f[0] = f[1] = 1;
  for (long long i = 2; i < 21; i++) f[i] = i * f[i - 1];
  long long t;
  cin >> t;
  while (t--) {
    long long k;
    cin >> k;
    cout << solve(k) << "\n";
  }
}
