#include <bits/stdc++.h>
using namespace std;
const long double pi = acos((long double)-1);
void in(initializer_list<int *> li) {
  for (auto ptr = li.begin(); ptr != li.end(); ptr++) scanf("%d", *ptr);
}
void in(initializer_list<long long *> li) {
  for (auto ptr = li.begin(); ptr != li.end(); ptr++) scanf("%lld", *ptr);
}
void in(initializer_list<double *> li) {
  for (auto ptr = li.begin(); ptr != li.end(); ptr++) scanf("%lf", *ptr);
}
void out(initializer_list<int> li) {
  for (auto ptr = li.begin(); ptr != li.end(); ptr++) printf("%d ", *ptr);
}
void outln(initializer_list<int> li) {
  for (auto ptr = li.begin(); ptr != li.end(); ptr++) printf("%d\n", *ptr);
}
void out(initializer_list<long long> li) {
  for (auto ptr = li.begin(); ptr != li.end(); ptr++) printf("%lld ", *ptr);
}
void outln(initializer_list<long long> li) {
  for (auto ptr = li.begin(); ptr != li.end(); ptr++) printf("%lld\n", *ptr);
}
int in(int &a, int &b, int &c, int &d) {
  return scanf("%d%d%d%d", &a, &b, &c, &d);
}
int in(int &a, int &b, int &c) { return scanf("%d%d%d", &a, &b, &c); }
int in(int &a, int &b) { return scanf("%d%d", &a, &b); }
int in(long long &a, long long &b) { return scanf("%lld%lld", &a, &b); }
int in(long long &a, long long &b, long long &c, long long &d) {
  return scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
}
int in(long long &a, long long &b, long long &c) {
  return scanf("%lld%lld%lld", &a, &b, &c);
}
int in(long long &a) { return scanf("%lld", &a); }
int in(int &a) { return scanf("%d", &a); }
int in(char *s) { return scanf("%s", s); }
int in(char &c) { return scanf("%c", &c); }
void out(int a, bool ln) { printf("%d%c", a, " \n"[ln]); }
void out(long long a, bool ln) { printf("%lld%c", a, " \n"[ln]); }
void out(double a, int digit, bool ln) {
  printf("%.*f%c", digit, a, " \n"[ln]);
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int maxn = 3e6 + 5;
const int maxm = 2e6 + 5;
const long long mod = 998244353;
long long a[maxn], cnt = 0;
vector<pair<long long, long long> > v;
long long c(long long a, long long b) {
  if (a < b) return 0;
  if (a == b) return 1;
  if (b > a - b) b = a - b;
  double cnm = 1.0;
  while (b > 0) cnm *= (double)(a--) / (double)(b--);
  cnm += 0.5;
  return (long long)cnm;
}
int main() {
  int TT;
  scanf("%d", &TT);
  for (int TTT = 1; TTT <= TT; TTT++) {
    long long n;
    in(n);
    cnt = 0;
    v.clear();
    int t = 2;
    while (n) {
      a[++cnt] = n % t;
      n /= t;
      t++;
    }
    sort(a + 1, a + cnt + 1);
    for (int i = 1; i <= cnt; ++i) {
      int j = i;
      while (j <= cnt && a[i] == a[j]) j++;
      v.push_back(pair<int, int>(a[i], j - i));
      i = j - 1;
    }
    long long ans = 1;
    n = v.size() - 1;
    long long x = 0;
    for (int i = n; i >= 0; --i) {
      int tt = cnt - v[i].first + 1 - x;
      if (v[i].first == 0) tt--;
      ans *= c(tt, v[i].second);
      x += v[i].second;
    }
    if (v[0].first == 0) {
      cnt--;
      v[0].second--;
      long long ans1 = 1;
      x = 0;
      for (int i = n; i >= 0; --i) {
        int tt = cnt - v[i].first + 1 - x;
        if (v[i].first == 0) tt--;
        ans1 *= c(tt, v[i].second);
        x += v[i].second;
      }
      ans -= ans1;
    }
    out(ans - 1, 1);
  }
  return 0;
}
