#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T sqr(const T &x) {
  return x * x;
}
inline long long sqr(int x) { return sqr<long long>(x); }
template <class T>
T binpow(const T &a, long long n) {
  return n == 0 ? 1 : sqr(binpow(a, n / 2)) * (n % 2 ? a : 1);
}
long long binpow(long long a, long long n, long long modulo) {
  return n == 0 ? 1
                : sqr(binpow(a, n / 2, modulo)) % modulo * (n % 2 ? a : 1) %
                      modulo;
}
long long gcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long d = gcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
inline long long phi(long long n) {
  long long result = n;
  for (long long i = 2; i * i <= n; ++i)
    if (n % i == 0) {
      while (n % i == 0) n /= i;
      result -= result / i;
    }
  if (n > 1) result -= result / n;
  return result;
}
inline vector<long long> inverseAll(long long m) {
  vector<long long> r(m);
  r[1] = 1;
  for (int i = 2; i < m; ++i) r[i] = (m - (m / i) * r[m % i] % m) % m;
  return r;
}
inline long long gcd(long long a, long long b) { return gcd(a, b, a, b); }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long llrand() {
  const long long lsbToFill = (sizeof(long long) << 3) - 1;
  const long long bitsFilledInIteration = __builtin_popcountll(RAND_MAX);
  long long number = 0;
  for (long long lsbFilled = 0; lsbFilled <= lsbToFill;
       lsbFilled += bitsFilledInIteration) {
    number ^= (((long long)rand()) << lsbFilled);
  }
  return number & numeric_limits<long long>::max();
}
inline long long llrand(long long begin, long long end) {
  return begin + llrand() % (end - begin);
}
struct Dinic {
  struct Edge {
    int u, v;
    long long cap, flow;
    Edge() {}
    Edge(int u, int v, long long cap) : u(u), v(v), cap(cap), flow(0) {}
  };
  int N;
  vector<Edge> E;
  vector<vector<int>> g;
  vector<int> d, pt;
  Dinic(int N) : N(N), E(0), g(N), d(N), pt(N) {}
  void AddEdge(int u, int v, long long cap) {
    if (u != v) {
      E.emplace_back(Edge(u, v, cap));
      g[u].emplace_back(E.size() - 1);
      E.emplace_back(Edge(v, u, 0));
      g[v].emplace_back(E.size() - 1);
    }
  }
  bool BFS(int S, int T) {
    queue<int> q({S});
    fill(d.begin(), d.end(), N + 1);
    d[S] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      if (u == T) break;
      for (int k : g[u]) {
        Edge &e = E[k];
        if (e.flow < e.cap && d[e.v] > d[e.u] + 1) {
          d[e.v] = d[e.u] + 1;
          q.emplace(e.v);
        }
      }
    }
    return d[T] != N + 1;
  }
  long long DFS(int u, int T, long long flow = -1) {
    if (u == T || flow == 0) return flow;
    for (int &i = pt[u]; i < g[u].size(); ++i) {
      Edge &e = E[g[u][i]];
      Edge &oe = E[g[u][i] ^ 1];
      if (d[e.v] == d[e.u] + 1) {
        long long amt = e.cap - e.flow;
        if (flow != -1 && amt > flow) amt = flow;
        if (long long pushed = DFS(e.v, T, amt)) {
          e.flow += pushed;
          oe.flow -= pushed;
          return pushed;
        }
      }
    }
    return 0;
  }
  long long MaxFlow(int S, int T) {
    long long total = 0;
    while (BFS(S, T)) {
      fill(pt.begin(), pt.end(), 0);
      while (long long flow = DFS(S, T)) total += flow;
    }
    return total;
  }
};
vector<long long> Dijkstra(const vector<list<pair<int, long long>>> &g, int s) {
  vector<long long> d(int((g).size()), numeric_limits<long long>::max() / 2LL);
  priority_queue<pair<long long, int>> q;
  d[s] = 0;
  q.emplace(-0, s);
  while (!q.empty()) {
    while (q.top().first > d[q.top().second]) {
      q.pop();
    }
    int v = q.top().second;
    q.pop();
    for (const auto &cw : g[v]) {
      if (d[v] + cw.second < d[cw.first]) {
        d[cw.first] = d[v] + cw.second;
        q.emplace(-d[cw.first], cw.first);
      }
    }
  }
  return d;
}
struct BinarySearchIterator
    : public std::iterator<std::forward_iterator_tag, bool> {
  long long value;
  typename iterator_traits<BinarySearchIterator>::difference_type operator-(
      const BinarySearchIterator &it) const {
    return value - it.value;
  }
  BinarySearchIterator &operator++() {
    ++value;
    return *this;
  }
  bool operator!=(const BinarySearchIterator &it) const {
    return value != it.value;
  }
  bool operator*() const { return true; }
};
template <int ALPHA>
class AhoCorasick {
 public:
  static const int ILLEGAL_INDEX;
  static const int ROOT;
  struct Node {
    bool leaf;
    int parent;
    int parentCharacter;
    int link;
    int next[ALPHA];
    int go[ALPHA];
    int outputFunction;
    Node(int parent = ILLEGAL_INDEX, int parentCharacter = ALPHA)
        : leaf(false),
          parent(parent),
          parentCharacter(parentCharacter),
          link(ILLEGAL_INDEX),
          outputFunction(ILLEGAL_INDEX) {
      fill_n(next, ALPHA, ILLEGAL_INDEX);
      fill_n(go, ALPHA, ILLEGAL_INDEX);
    }
  };
  vector<Node> tree = vector<Node>(1);
  AhoCorasick() {}
  AhoCorasick(int maxStatesNumber) { tree.reserve(maxStatesNumber); }
  template <class Iterator>
  void add(int length, const Iterator begin) {
    int vertex = ROOT;
    for (int i = 0; i < length; ++i) {
      if (ILLEGAL_INDEX == tree[vertex].next[begin[i]]) {
        tree[vertex].next[begin[i]] = int((tree).size());
        tree.push_back(Node(vertex, begin[i]));
      }
      vertex = tree[vertex].next[begin[i]];
    }
    tree[vertex].leaf = true;
  }
  int getLink(int vertex) {
    assert(0 <= vertex && vertex < tree.size());
    if (ILLEGAL_INDEX == tree[vertex].link) {
      if (ROOT == vertex || ROOT == tree[vertex].parent) {
        tree[vertex].link = ROOT;
      } else {
        tree[vertex].link =
            go(getLink(tree[vertex].parent), tree[vertex].parentCharacter);
      }
    }
    return tree[vertex].link;
  }
  int go(int vertex, int character) {
    assert(0 <= character && character < ALPHA);
    assert(0 <= vertex && vertex < tree.size());
    if (ILLEGAL_INDEX == tree[vertex].go[character]) {
      if (ILLEGAL_INDEX == tree[vertex].next[character]) {
        tree[vertex].go[character] =
            ROOT == vertex ? ROOT : go(getLink(vertex), character);
      } else {
        tree[vertex].go[character] = tree[vertex].next[character];
      }
    }
    return tree[vertex].go[character];
  }
  int getOutputFunction(int vertex) {
    assert(0 <= vertex && vertex < tree.size());
    if (ILLEGAL_INDEX == tree[vertex].outputFunction) {
      if (tree[vertex].leaf || ROOT == vertex) {
        tree[vertex].outputFunction = vertex;
      } else {
        tree[vertex].outputFunction = getOutputFunction(getLink(vertex));
      }
    }
    return tree[vertex].outputFunction;
  }
};
template <int ALPHA>
const int AhoCorasick<ALPHA>::ILLEGAL_INDEX = -1;
template <int ALPHA>
const int AhoCorasick<ALPHA>::ROOT = 0;
struct UnionFind {
  vector<int> parent;
  vector<int> rank;
  UnionFind(int n) : parent(n), rank(n) {
    for (int i = 0; i < n; ++i) {
      parent[i] = i;
      rank[i] = 0;
    }
  }
  int find_set(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find_set(parent[v]);
  }
  void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
      if (rank[a] < rank[b]) swap(a, b);
      parent[b] = a;
      if (rank[a] == rank[b]) ++rank[a];
    }
  }
};
template <class T>
T assign(const T &, const T &t) {
  return t;
}
template <class T>
struct SegmentTree {
  int n;
  vector<T> t;
  function<T(const T &, const T &)> operation;
  T default_value;
  function<T(const T &, const T &)> modification;
  SegmentTree() {}
  SegmentTree(const int n, const function<T(T, T)> &operation,
              const T &default_value = T(),
              const function<T(T, T)> &modification = assign<T>)
      : n(n),
        t(n << 1),
        operation(operation),
        default_value(default_value),
        modification(modification) {}
  SegmentTree(const vector<T> &a, const function<T(T, T)> &operation,
              const T &default_value = T(),
              const function<T(T, T)> &modification = assign<T>)
      : SegmentTree(int((a).size()), operation, default_value, modification) {
    copy((a).begin(), (a).end(), t.begin() + n);
    for (int i = n - 1; i > 0; --i) t[i] = operation(t[i << 1], t[i << 1 | 1]);
  }
  void modify(int p, T value) {
    p += n;
    for (t[p] = modification(t[p], value); p > 1; p >>= 1)
      t[p >> 1] = operation(t[p], t[p ^ 1]);
  }
  T query(int l, int r) const {
    T res = default_value;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res = operation(res, t[l++]);
      if (r & 1) res = operation(res, t[--r]);
    }
    return res;
  }
};
long long factorial[21];
long long choose(int n, int k) {
  return n < k ? 0 : factorial[n] / factorial[n - k] / factorial[k];
}
long long solve(const map<int, int> &reminder2count, int max_position) {
  long long answer = 1;
  int already = 0;
  for (auto it = reminder2count.rbegin(); it != reminder2count.rend(); ++it) {
    if (it->second) {
      int top = max_position - max(1, it->first) - already;
      int bottom = it->second;
      answer *= choose(top, bottom);
      already += it->second;
    }
  }
  return answer;
}
long long solve(long long k) {
  int i;
  map<int, int> reminder2count;
  for (i = 2; k; ++i) {
    ++reminder2count[k % i];
    k /= i;
  }
  --i;
  long long all = solve(reminder2count, i);
  long long bad = 0;
  if (reminder2count[0] > 0) {
    --reminder2count[0];
    bad = solve(reminder2count, i - 1);
  }
  return all - bad - 1;
}
int main(int argc, const char *argv[]) {
  factorial[0] = 1;
  for (int i = 1; i < sizeof(factorial) / sizeof(*factorial); ++i) {
    factorial[i] = factorial[i - 1] * i;
  }
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(13);
  cout.setf(ios::fixed);
  srand((unsigned int)time(NULL));
  int t;
  cin >> t;
  for (int test = (0); test < (t); ++test) {
    long long k;
    cin >> k;
    cout << solve(k) << endl;
  }
  return 0;
}

### Prompt

Your task is to create a cpp solution to the following problem:

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>
using namespace std;
template <class T>
inline T sqr(const T &x) {
  return x * x;
}
inline long long sqr(int x) { return sqr<long long>(x); }
template <class T>
T binpow(const T &a, long long n) {
  return n == 0 ? 1 : sqr(binpow(a, n / 2)) * (n % 2 ? a : 1);
}
long long binpow(long long a, long long n, long long modulo) {
  return n == 0 ? 1
                : sqr(binpow(a, n / 2, modulo)) % modulo * (n % 2 ? a : 1) %
                      modulo;
}
long long gcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long d = gcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
inline long long phi(long long n) {
  long long result = n;
  for (long long i = 2; i * i <= n; ++i)
    if (n % i == 0) {
      while (n % i == 0) n /= i;
      result -= result / i;
    }
  if (n > 1) result -= result / n;
  return result;
}
inline vector<long long> inverseAll(long long m) {
  vector<long long> r(m);
  r[1] = 1;
  for (int i = 2; i < m; ++i) r[i] = (m - (m / i) * r[m % i] % m) % m;
  return r;
}
inline long long gcd(long long a, long long b) { return gcd(a, b, a, b); }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long llrand() {
  const long long lsbToFill = (sizeof(long long) << 3) - 1;
  const long long bitsFilledInIteration = __builtin_popcountll(RAND_MAX);
  long long number = 0;
  for (long long lsbFilled = 0; lsbFilled <= lsbToFill;
       lsbFilled += bitsFilledInIteration) {
    number ^= (((long long)rand()) << lsbFilled);
  }
  return number & numeric_limits<long long>::max();
}
inline long long llrand(long long begin, long long end) {
  return begin + llrand() % (end - begin);
}
struct Dinic {
  struct Edge {
    int u, v;
    long long cap, flow;
    Edge() {}
    Edge(int u, int v, long long cap) : u(u), v(v), cap(cap), flow(0) {}
  };
  int N;
  vector<Edge> E;
  vector<vector<int>> g;
  vector<int> d, pt;
  Dinic(int N) : N(N), E(0), g(N), d(N), pt(N) {}
  void AddEdge(int u, int v, long long cap) {
    if (u != v) {
      E.emplace_back(Edge(u, v, cap));
      g[u].emplace_back(E.size() - 1);
      E.emplace_back(Edge(v, u, 0));
      g[v].emplace_back(E.size() - 1);
    }
  }
  bool BFS(int S, int T) {
    queue<int> q({S});
    fill(d.begin(), d.end(), N + 1);
    d[S] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      if (u == T) break;
      for (int k : g[u]) {
        Edge &e = E[k];
        if (e.flow < e.cap && d[e.v] > d[e.u] + 1) {
          d[e.v] = d[e.u] + 1;
          q.emplace(e.v);
        }
      }
    }
    return d[T] != N + 1;
  }
  long long DFS(int u, int T, long long flow = -1) {
    if (u == T || flow == 0) return flow;
    for (int &i = pt[u]; i < g[u].size(); ++i) {
      Edge &e = E[g[u][i]];
      Edge &oe = E[g[u][i] ^ 1];
      if (d[e.v] == d[e.u] + 1) {
        long long amt = e.cap - e.flow;
        if (flow != -1 && amt > flow) amt = flow;
        if (long long pushed = DFS(e.v, T, amt)) {
          e.flow += pushed;
          oe.flow -= pushed;
          return pushed;
        }
      }
    }
    return 0;
  }
  long long MaxFlow(int S, int T) {
    long long total = 0;
    while (BFS(S, T)) {
      fill(pt.begin(), pt.end(), 0);
      while (long long flow = DFS(S, T)) total += flow;
    }
    return total;
  }
};
vector<long long> Dijkstra(const vector<list<pair<int, long long>>> &g, int s) {
  vector<long long> d(int((g).size()), numeric_limits<long long>::max() / 2LL);
  priority_queue<pair<long long, int>> q;
  d[s] = 0;
  q.emplace(-0, s);
  while (!q.empty()) {
    while (q.top().first > d[q.top().second]) {
      q.pop();
    }
    int v = q.top().second;
    q.pop();
    for (const auto &cw : g[v]) {
      if (d[v] + cw.second < d[cw.first]) {
        d[cw.first] = d[v] + cw.second;
        q.emplace(-d[cw.first], cw.first);
      }
    }
  }
  return d;
}
struct BinarySearchIterator
    : public std::iterator<std::forward_iterator_tag, bool> {
  long long value;
  typename iterator_traits<BinarySearchIterator>::difference_type operator-(
      const BinarySearchIterator &it) const {
    return value - it.value;
  }
  BinarySearchIterator &operator++() {
    ++value;
    return *this;
  }
  bool operator!=(const BinarySearchIterator &it) const {
    return value != it.value;
  }
  bool operator*() const { return true; }
};
template <int ALPHA>
class AhoCorasick {
 public:
  static const int ILLEGAL_INDEX;
  static const int ROOT;
  struct Node {
    bool leaf;
    int parent;
    int parentCharacter;
    int link;
    int next[ALPHA];
    int go[ALPHA];
    int outputFunction;
    Node(int parent = ILLEGAL_INDEX, int parentCharacter = ALPHA)
        : leaf(false),
          parent(parent),
          parentCharacter(parentCharacter),
          link(ILLEGAL_INDEX),
          outputFunction(ILLEGAL_INDEX) {
      fill_n(next, ALPHA, ILLEGAL_INDEX);
      fill_n(go, ALPHA, ILLEGAL_INDEX);
    }
  };
  vector<Node> tree = vector<Node>(1);
  AhoCorasick() {}
  AhoCorasick(int maxStatesNumber) { tree.reserve(maxStatesNumber); }
  template <class Iterator>
  void add(int length, const Iterator begin) {
    int vertex = ROOT;
    for (int i = 0; i < length; ++i) {
      if (ILLEGAL_INDEX == tree[vertex].next[begin[i]]) {
        tree[vertex].next[begin[i]] = int((tree).size());
        tree.push_back(Node(vertex, begin[i]));
      }
      vertex = tree[vertex].next[begin[i]];
    }
    tree[vertex].leaf = true;
  }
  int getLink(int vertex) {
    assert(0 <= vertex && vertex < tree.size());
    if (ILLEGAL_INDEX == tree[vertex].link) {
      if (ROOT == vertex || ROOT == tree[vertex].parent) {
        tree[vertex].link = ROOT;
      } else {
        tree[vertex].link =
            go(getLink(tree[vertex].parent), tree[vertex].parentCharacter);
      }
    }
    return tree[vertex].link;
  }
  int go(int vertex, int character) {
    assert(0 <= character && character < ALPHA);
    assert(0 <= vertex && vertex < tree.size());
    if (ILLEGAL_INDEX == tree[vertex].go[character]) {
      if (ILLEGAL_INDEX == tree[vertex].next[character]) {
        tree[vertex].go[character] =
            ROOT == vertex ? ROOT : go(getLink(vertex), character);
      } else {
        tree[vertex].go[character] = tree[vertex].next[character];
      }
    }
    return tree[vertex].go[character];
  }
  int getOutputFunction(int vertex) {
    assert(0 <= vertex && vertex < tree.size());
    if (ILLEGAL_INDEX == tree[vertex].outputFunction) {
      if (tree[vertex].leaf || ROOT == vertex) {
        tree[vertex].outputFunction = vertex;
      } else {
        tree[vertex].outputFunction = getOutputFunction(getLink(vertex));
      }
    }
    return tree[vertex].outputFunction;
  }
};
template <int ALPHA>
const int AhoCorasick<ALPHA>::ILLEGAL_INDEX = -1;
template <int ALPHA>
const int AhoCorasick<ALPHA>::ROOT = 0;
struct UnionFind {
  vector<int> parent;
  vector<int> rank;
  UnionFind(int n) : parent(n), rank(n) {
    for (int i = 0; i < n; ++i) {
      parent[i] = i;
      rank[i] = 0;
    }
  }
  int find_set(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find_set(parent[v]);
  }
  void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
      if (rank[a] < rank[b]) swap(a, b);
      parent[b] = a;
      if (rank[a] == rank[b]) ++rank[a];
    }
  }
};
template <class T>
T assign(const T &, const T &t) {
  return t;
}
template <class T>
struct SegmentTree {
  int n;
  vector<T> t;
  function<T(const T &, const T &)> operation;
  T default_value;
  function<T(const T &, const T &)> modification;
  SegmentTree() {}
  SegmentTree(const int n, const function<T(T, T)> &operation,
              const T &default_value = T(),
              const function<T(T, T)> &modification = assign<T>)
      : n(n),
        t(n << 1),
        operation(operation),
        default_value(default_value),
        modification(modification) {}
  SegmentTree(const vector<T> &a, const function<T(T, T)> &operation,
              const T &default_value = T(),
              const function<T(T, T)> &modification = assign<T>)
      : SegmentTree(int((a).size()), operation, default_value, modification) {
    copy((a).begin(), (a).end(), t.begin() + n);
    for (int i = n - 1; i > 0; --i) t[i] = operation(t[i << 1], t[i << 1 | 1]);
  }
  void modify(int p, T value) {
    p += n;
    for (t[p] = modification(t[p], value); p > 1; p >>= 1)
      t[p >> 1] = operation(t[p], t[p ^ 1]);
  }
  T query(int l, int r) const {
    T res = default_value;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res = operation(res, t[l++]);
      if (r & 1) res = operation(res, t[--r]);
    }
    return res;
  }
};
long long factorial[21];
long long choose(int n, int k) {
  return n < k ? 0 : factorial[n] / factorial[n - k] / factorial[k];
}
long long solve(const map<int, int> &reminder2count, int max_position) {
  long long answer = 1;
  int already = 0;
  for (auto it = reminder2count.rbegin(); it != reminder2count.rend(); ++it) {
    if (it->second) {
      int top = max_position - max(1, it->first) - already;
      int bottom = it->second;
      answer *= choose(top, bottom);
      already += it->second;
    }
  }
  return answer;
}
long long solve(long long k) {
  int i;
  map<int, int> reminder2count;
  for (i = 2; k; ++i) {
    ++reminder2count[k % i];
    k /= i;
  }
  --i;
  long long all = solve(reminder2count, i);
  long long bad = 0;
  if (reminder2count[0] > 0) {
    --reminder2count[0];
    bad = solve(reminder2count, i - 1);
  }
  return all - bad - 1;
}
int main(int argc, const char *argv[]) {
  factorial[0] = 1;
  for (int i = 1; i < sizeof(factorial) / sizeof(*factorial); ++i) {
    factorial[i] = factorial[i - 1] * i;
  }
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(13);
  cout.setf(ios::fixed);
  srand((unsigned int)time(NULL));
  int t;
  cin >> t;
  for (int test = (0); test < (t); ++test) {
    long long k;
    cin >> k;
    cout << solve(k) << endl;
  }
  return 0;
}

```