#include <bits/stdc++.h>
using namespace std;
const int M = 21;
long long factor[M];
long long nCk(int n, int k) {
  if (n < 0 || k < 0 || n < k) return 0;
  return factor[n] / factor[k] / factor[n - k];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int cnt[M], ntest, div, sum, bit;
  long long k, ans, add;
  factor[0] = 1;
  for (int i = 1; i < M; ++i) factor[i] = factor[i - 1] * i;
  cin >> ntest;
  while (ntest--) {
    cin >> k;
    fill(cnt, cnt + 20, 0);
    div = 1;
    while (k) {
      ++div;
      ++cnt[k % div];
      k /= div;
    }
    ans = 0;
    for (int i = div - 1; i >= 1; --i) {
      if (cnt[i]) {
        --cnt[i];
        add = (cnt[div - 1] == 0);
        bit = 0;
        for (int j = div - 2; j >= 1; --j) {
          ++bit;
          if (cnt[j]) {
            add *= nCk(bit, cnt[j]);
            bit -= cnt[j];
          }
        }
        ans += add;
        ++cnt[i];
      }
    }
    cout << ans - 1 << '\n';
  }
  return 0;
}
