#include <bits/stdc++.h>
long long dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
long long dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
using namespace std;
class pa3 {
 public:
  long long x;
  long long y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3 &p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3 &p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4 &p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2 &p) const { return y != p.y ? y < p.y : x < p.x; }
  bool operator>(const pa2 &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const pa2 &p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2 &p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long gcd(long long v, long long b) {
  if (v == 0) return b;
  if (b == 0) return v;
  if (v > b) return gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return gcd(v, b % v);
}
long long mod;
long long extgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
pair<long long, long long> operator+(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first + r.first, l.second + r.second};
}
pair<long long, long long> operator-(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first - r.first, l.second - r.second};
}
long long pr[10000100];
long long inv[10000010];
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  wa %= warukazu;
  if (rr % 2 == 1)
    return ((long long)beki(wa, rr - 1, warukazu) * (long long)wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
long long comb(long long nn, long long rr) {
  if (rr < 0 || rr > nn || nn < 0) return 0;
  long long r = pr[nn] * inv[rr];
  r %= mod;
  r *= inv[nn - rr];
  r %= mod;
  return r;
}
void gya(long long ert) {
  pr[0] = 1;
  for (long long i = 1; i <= ert; i++) {
    pr[i] = ((long long)pr[i - 1] * i) % mod;
  }
  inv[ert] = beki(pr[ert], mod - 2, mod);
  for (long long i = ert - 1; i >= 0; i--) {
    inv[i] = (long long)inv[i + 1] * (i + 1) % mod;
  }
}
vector<long long> solve(long long n) {
  long long c = 2;
  vector<long long> ve;
  while (n) {
    ve.push_back(n % c);
    n /= c;
    c++;
  }
  sort(ve.begin(), ve.end());
  return ve;
}
long long toku(vector<long long> ve) {
  if (ve.size() == 0) return 1;
  sort(ve.begin(), ve.end(), greater<long long>());
  long long n = ve.size();
  long long mae = 0;
  long long aki = 0;
  long long ans = 1;
  long long maev = -1;
  long long waru = 1;
  long long ren = 0;
  if (ve[0] > n) return 0;
  long long ok[30];
  ok[0] = n;
  ok[1] = n;
  for (long long i = 1; n + 1 - i > 0; i++) ok[i] = n + 1 - i;
  for (long long i = 0; i < n; i++) {
    long long sa = -mae + ok[ve[i]];
    if (maev == ve[i])
      ren++;
    else
      ren = 1;
    aki += sa;
    ans *= aki;
    waru *= ren;
    if (ren > 1) {
      long long g = gcd(ans, ren);
      ans /= g;
      waru /= g;
    }
    aki--;
    mae = ok[ve[i]];
    maev = ve[i];
  }
  return ans;
}
long long yaru(long long n) {
  long long c = 2;
  long long a[25] = {};
  while (n) {
    a[n % c]++;
    n /= c;
    c++;
  }
  long long ans = 0;
  for (long long i = 1; i < 25; i++)
    if (a[i]) {
      vector<long long> ve;
      for (long long j = 0; j < 25; j++)
        if (a[j]) {
          for (long long k = 0; k < a[j] - (i == j); k++) ve.push_back(j);
        }
      ans += toku(ve);
    }
  return ans;
}
long long modosu(vector<long long> ve) {
  long long n = ve.size();
  long long ans = 0;
  for (long long i = n - 1; i >= 0; i--) {
    ans *= i + 2;
    ans += ve[i];
  }
  return ans;
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n;
  cin >> n;
  for (long long i = 0; i < n; i++) {
    long long y;
    cin >> y;
    cout << yaru(y) - 1 << endl;
  }
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

Karl is developing a key storage service. Each user has a positive integer key.

Karl knows that storing keys in plain text is bad practice. So, instead of storing a key, he decided to store a fingerprint of a key. However, using some existing fingerprint algorithm looked too boring to him, so he invented his own one.

Karl's fingerprint is calculated by the following process: divide the given integer by 2, then divide the result by 3, then divide the result by 4, and so on, until we get a result that equals zero (we are speaking about integer division each time). The fingerprint is defined as the multiset of the remainders of these divisions. 

For example, this is how Karl's fingerprint algorithm is applied to the key 11: 11 divided by 2 has remainder 1 and result 5, then 5 divided by 3 has remainder 2 and result 1, and 1 divided by 4 has remainder 1 and result 0. Thus, the key 11 produces the sequence of remainders [1, 2, 1] and has the fingerprint multiset \{1, 1, 2\}.

Ksenia wants to prove that Karl's fingerprint algorithm is not very good. For example, she found that both keys 178800 and 123456 produce the fingerprint of \{0, 0, 0, 0, 2, 3, 3, 4\}. Thus, users are at risk of fingerprint collision with some commonly used and easy to guess keys like 123456.

Ksenia wants to make her words more persuasive. She wants to calculate the number of other keys that have the same fingerprint as the keys in the given list of some commonly used keys. Your task is to help her.

Input

The first line contains an integer t (1 ≤ t ≤ 50 000) — the number of commonly used keys to examine. Each of the next t lines contains one integer k_i (1 ≤ k_i ≤ 10^{18}) — the key itself. 

Output

For each of the keys print one integer — the number of other keys that have the same fingerprint. 

Example

Input


3
1
11
123456


Output


0
1
127

Note

The other key with the same fingerprint as 11 is 15. 15 produces a sequence of remainders [1, 1, 2]. So both numbers have the fingerprint multiset \{1, 1, 2\}.

### Response

```cpp
#include <bits/stdc++.h>
long long dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
long long dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
using namespace std;
class pa3 {
 public:
  long long x;
  long long y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3 &p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3 &p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4 &p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2 &p) const { return y != p.y ? y < p.y : x < p.x; }
  bool operator>(const pa2 &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const pa2 &p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2 &p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long gcd(long long v, long long b) {
  if (v == 0) return b;
  if (b == 0) return v;
  if (v > b) return gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return gcd(v, b % v);
}
long long mod;
long long extgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
pair<long long, long long> operator+(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first + r.first, l.second + r.second};
}
pair<long long, long long> operator-(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first - r.first, l.second - r.second};
}
long long pr[10000100];
long long inv[10000010];
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  wa %= warukazu;
  if (rr % 2 == 1)
    return ((long long)beki(wa, rr - 1, warukazu) * (long long)wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
long long comb(long long nn, long long rr) {
  if (rr < 0 || rr > nn || nn < 0) return 0;
  long long r = pr[nn] * inv[rr];
  r %= mod;
  r *= inv[nn - rr];
  r %= mod;
  return r;
}
void gya(long long ert) {
  pr[0] = 1;
  for (long long i = 1; i <= ert; i++) {
    pr[i] = ((long long)pr[i - 1] * i) % mod;
  }
  inv[ert] = beki(pr[ert], mod - 2, mod);
  for (long long i = ert - 1; i >= 0; i--) {
    inv[i] = (long long)inv[i + 1] * (i + 1) % mod;
  }
}
vector<long long> solve(long long n) {
  long long c = 2;
  vector<long long> ve;
  while (n) {
    ve.push_back(n % c);
    n /= c;
    c++;
  }
  sort(ve.begin(), ve.end());
  return ve;
}
long long toku(vector<long long> ve) {
  if (ve.size() == 0) return 1;
  sort(ve.begin(), ve.end(), greater<long long>());
  long long n = ve.size();
  long long mae = 0;
  long long aki = 0;
  long long ans = 1;
  long long maev = -1;
  long long waru = 1;
  long long ren = 0;
  if (ve[0] > n) return 0;
  long long ok[30];
  ok[0] = n;
  ok[1] = n;
  for (long long i = 1; n + 1 - i > 0; i++) ok[i] = n + 1 - i;
  for (long long i = 0; i < n; i++) {
    long long sa = -mae + ok[ve[i]];
    if (maev == ve[i])
      ren++;
    else
      ren = 1;
    aki += sa;
    ans *= aki;
    waru *= ren;
    if (ren > 1) {
      long long g = gcd(ans, ren);
      ans /= g;
      waru /= g;
    }
    aki--;
    mae = ok[ve[i]];
    maev = ve[i];
  }
  return ans;
}
long long yaru(long long n) {
  long long c = 2;
  long long a[25] = {};
  while (n) {
    a[n % c]++;
    n /= c;
    c++;
  }
  long long ans = 0;
  for (long long i = 1; i < 25; i++)
    if (a[i]) {
      vector<long long> ve;
      for (long long j = 0; j < 25; j++)
        if (a[j]) {
          for (long long k = 0; k < a[j] - (i == j); k++) ve.push_back(j);
        }
      ans += toku(ve);
    }
  return ans;
}
long long modosu(vector<long long> ve) {
  long long n = ve.size();
  long long ans = 0;
  for (long long i = n - 1; i >= 0; i--) {
    ans *= i + 2;
    ans += ve[i];
  }
  return ans;
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n;
  cin >> n;
  for (long long i = 0; i < n; i++) {
    long long y;
    cin >> y;
    cout << yaru(y) - 1 << endl;
  }
  return 0;
}

```