#include <bits/stdc++.h>
using i64 = long long;
const int MAXN = 25;
int t;
i64 n;
std::vector<int> encode(i64 x) {
  std::vector<int> result;
  for (int i = 2; x; ++i) {
    i64 r = x / i, m = x % i;
    result.push_back(m);
    x = r;
  }
  return result;
}
i64 decode(const std::vector<int>& vec) {
  i64 result = 0;
  for (int i = int(vec.size()) - 1; i >= 0; --i)
    result = result * (i + 2) + vec[i];
  return result;
}
void print(const std::vector<int>& vec) {
  for (int i = 0; i < int(vec.size()); ++i)
    std::cout << vec[i] << " \n"[i == int(vec.size()) - 1];
}
i64 cc[MAXN][MAXN];
i64 solve(const std::vector<int>& vec) {
  i64 result = 1;
  int r = int(vec.size()) - 1;
  for (int i = 0; i < int(vec.size()); ++i)
    if (vec[i] >= i + 2) return 0;
  while (true) {
    int l = r;
    while (l && vec[l - 1] == vec[r]) --l;
    if (!l) break;
    int a = r - vec[r] + 2, b = r - l + 1;
    if (a < b) return 0;
    result *= cc[a][b];
    r = l - 1;
  }
  return result;
}
int main() {
  cc[0][0] = 1;
  for (int i = 1; i < MAXN; ++i) {
    cc[i][0] = cc[i][i] = 1;
    for (int j = 1; j < i; ++j) cc[i][j] = cc[i - 1][j - 1] + cc[i - 1][j];
  }
  std::scanf("%d", &t);
  for (int test = 0; test < t; ++test) {
    std::scanf("%lld", &n);
    std::vector<int> vec = encode(n);
    std::sort(vec.begin(), vec.end());
    i64 result = solve(vec);
    if (!vec[0]) {
      std::vector<int> vec2(vec.begin() + 1, vec.end());
      result -= solve(vec2);
    }
    std::printf("%lld\n", result - 1);
  }
}
