#include <bits/stdc++.h>
using namespace std;
unsigned long long p[50], dp[50];
int A[50], sum[50], cnt = 0;
int main() {
  int i, t, j;
  long long n, a, b;
  p[0] = 1;
  for (i = 1; i <= 30; i++) p[i] = p[i - 1] * i;
  scanf("%d", &t);
  while (t--) {
    scanf("%lld", &n);
    cnt = 0;
    a = 1;
    while (n) {
      a++;
      A[++cnt] = n % a;
      n /= a;
    }
    int last = 0, now;
    dp[1] = 1;
    sort(A + 1, A + 1 + cnt);
    memset(sum, 0, sizeof(sum));
    for (i = 1; i <= cnt; i++) sum[A[i]]++;
    for (i = 2; i <= a; i++) {
      now = 0;
      for (j = 1; j <= cnt; j++)
        if (A[j] < i) now = j;
      dp[i] = dp[i - 1] * (now - last) + (last - (i - 2)) * dp[i - 1];
      last = now;
    }
    for (i = 0; i <= 30; i++) dp[a] /= p[sum[i]];
    long long ans = dp[a];
    if (cnt > 1 && A[1] == 0) {
      swap(A[1], A[cnt]);
      cnt--;
      sort(A + 1, A + 1 + cnt);
      memset(sum, 0, sizeof(sum));
      for (i = 1; i <= cnt; i++) sum[A[i]]++;
      last = 0;
      for (i = 2; i < a; i++) {
        now = 0;
        for (j = 1; j <= cnt; j++)
          if (A[j] < i) now = j;
        dp[i] = dp[i - 1] * (now - last) + (last - (i - 2)) * dp[i - 1];
        last = now;
      }
      for (i = 0; i <= 30; i++) dp[a - 1] /= p[sum[i]];
      ans -= dp[a - 1];
    }
    cout << ans - 1 << endl;
  }
  return 0;
}
