#include <bits/stdc++.h>
using namespace std;
long long C(long long n, long long r) {
  if (r > n) return 0;
  long long res = 1;
  for (long long i = 1; i <= r; i++) res *= (n - i + 1), res /= i;
  return res;
}
int t;
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> t;
  while (t--) {
    long long n;
    cin >> n;
    vector<int> v;
    int ind = 2;
    bool flag = false;
    while (n > 0) {
      v.push_back(n % ind);
      if (n % ind == 0) flag = true;
      n /= ind++;
    }
    v.push_back(-1);
    sort(v.begin(), v.end());
    long long cnt = 1, ans = 1, mot = 0;
    for (int i = (int)v.size() - 2; i >= 0; i--)
      if (v[i] != v[i + 1]) {
        if (v[i] == -1) continue;
        long long p = (int)v.size() - v[i + 1], tmp = (int)v.size() - i - 1;
        tmp -= cnt;
        ans *= C(p - tmp, cnt);
        cnt = 1;
      } else
        cnt++;
    if (flag) {
      cnt = 1, mot = 1;
      for (int i = 0; i < v.size(); i++)
        if (v[i] == 0) {
          swap(v[i], v[v.size() - 1]);
          break;
        }
      v.pop_back();
      sort(v.begin(), v.end());
      for (int i = (int)v.size() - 2; i >= 0; i--)
        if (v[i] != v[i + 1]) {
          if (v[i] == -1 && v[i + 1] == 0) continue;
          long long p = (int)v.size() - v[i + 1], tmp = (int)v.size() - i - 1;
          tmp -= cnt;
          mot *= C(p - tmp, cnt);
          cnt = 1;
        } else
          cnt++;
    }
    cout << ans - 1 - mot << endl;
  }
  return 0;
}
