#include <bits/stdc++.h>
using namespace std;
template <typename T>
void debug_out(T t) {
  cerr << t;
}
template <typename A, typename B>
void debug_out(pair<A, B> u) {
  cerr << "(" << u.first << " " << u.second << ")";
}
template <typename T>
void debug_out(vector<T> t) {
  int sz = t.size();
  for (int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if (i != sz - 1) cerr << ", ";
  }
}
template <typename T>
void debug_out(vector<vector<T>> t) {
  int sz = t.size();
  for (int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if (i != sz - 1) cerr << endl;
  }
}
template <typename T>
class graph {
 public:
  struct edge {
    int from;
    int to;
    int num;
    int id;
    T cost;
  };
  vector<edge> edges;
  vector<vector<int>> g;
  int n;
  graph(int _n) : n(_n) { g.resize(n); }
  virtual int add(int from, int to, int num, T cost) = 0;
};
template <typename T>
class digraph : public graph<T> {
 public:
  using graph<T>::edges;
  using graph<T>::g;
  using graph<T>::n;
  digraph(int _n) : graph<T>(_n) {}
  int add(int from, int to, int num, T cost = 1) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    int id = (int)edges.size();
    g[from].push_back(id);
    edges.push_back({from, to, num, id, cost});
    return id;
  }
  digraph<T> reverse() const {
    digraph<T> rev(n);
    for (auto &e : edges) {
      rev.add(e.to, e.from, e.cost);
    }
    return rev;
  }
};
const int n = 1000;
const int m = 4;
const int inf = INT_MAX;
int a;
digraph<int> st(n);
void relax(vector<int> &dep, vector<vector<int>> &par) {
  vector<int> _dep(n, inf);
  vector<int> _par(n, -1);
  for (auto e : st.edges) {
    if (dep[e.from] < inf && _dep[e.to] > dep[e.from] + e.cost) {
      _dep[e.to] = dep[e.from] + e.cost;
      _par[e.to] = e.id;
    }
  }
  swap(dep, _dep);
  par.push_back(_par);
}
void solve(vector<vector<int>> &par, vector<vector<int>> &dp) {
  dp.resize(1);
  par.resize(1);
  dp[0].resize(n, inf);
  par[0].resize(n, -1);
  dp[0][0] = 0;
  vector<int> _dp = dp[0];
  while (par.size() < m * n) {
    relax(_dp, par);
    dp.push_back(_dp);
  }
}
int digit(int v) {
  return (v % 10) + ((v / 10) % 10) + ((v / 100) % 10) + ((v / 1000) % 10);
}
struct use {
  int dep, dif, id, type;
  use(){};
  use(int _dep, int _dif, int _id, int _type)
      : dep(_dep), dif(_dif), id(_id), type(_type){};
};
void debug_out(use a) {
  debug_out(a.dep);
  cerr << " ";
  debug_out(a.dif);
  cerr << " ";
  debug_out(a.id);
  cerr << " ";
  debug_out(a.type);
}
int main() {
  cin >> a;
  if (a == 2) {
    cout << 6;
    return 0;
  }
  if (a == 3) {
    cout << 6669;
    return 0;
  }
  if (a == 6) {
    cout << 8333333333333334;
    return 0;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 10; j++) {
      int w = j - a * (digit(j * a + i) - digit(i));
      int v = (j * a + i) / 10;
      if (i || j) st.add(i, v, j, w);
    }
  }
  vector<vector<int>> pos, ps;
  solve(pos, ps);
  for (auto &i : st.edges) {
    i.cost *= -1;
  }
  vector<vector<int>> neg, ns;
  solve(neg, ns);
  auto track = [&](int v, int dep, vector<vector<int>> &par) {
    vector<int> res;
    while (dep) {
      res.push_back(st.edges[par[dep][v]].num);
      v = st.edges[par[dep][v]].from;
      dep--;
    }
    reverse(res.begin(), res.end());
    while (!res.back()) res.pop_back();
    reverse(res.begin(), res.end());
    return res;
  };
  for (int rot = 0; rot < 2; rot++) {
    for (int i = 0; i < m * n; i++) {
      for (int j = 0; j < n; j++) {
        if (!i && !j) continue;
        if (!ps[i][j]) {
          vector<int> res = track(j, i, pos);
          for (auto x : res) printf("%d", x);
          cerr << endl;
          return 0;
        }
      }
    }
    swap(ps, ns);
    swap(pos, neg);
  }
  cout << -1;
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

A positive integer a is given. Baron Munchausen claims that he knows such a positive integer n that if one multiplies n by a, the sum of its digits decreases a times. In other words, S(an) = S(n)/a, where S(x) denotes the sum of digits of the number x. 

Find out if what Baron told can be true.

Input

The only line contains a single integer a (2 ≤ a ≤ 10^3).

Output

If there is no such number n, print -1.

Otherwise print any appropriate positive integer n. Your number must not consist of more than 5⋅10^5 digits. We can show that under given constraints either there is no answer, or there is an answer no longer than 5⋅10^5 digits.

Examples

Input


2


Output


6


Input


3


Output


6669


Input


10


Output


-1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
void debug_out(T t) {
  cerr << t;
}
template <typename A, typename B>
void debug_out(pair<A, B> u) {
  cerr << "(" << u.first << " " << u.second << ")";
}
template <typename T>
void debug_out(vector<T> t) {
  int sz = t.size();
  for (int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if (i != sz - 1) cerr << ", ";
  }
}
template <typename T>
void debug_out(vector<vector<T>> t) {
  int sz = t.size();
  for (int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if (i != sz - 1) cerr << endl;
  }
}
template <typename T>
class graph {
 public:
  struct edge {
    int from;
    int to;
    int num;
    int id;
    T cost;
  };
  vector<edge> edges;
  vector<vector<int>> g;
  int n;
  graph(int _n) : n(_n) { g.resize(n); }
  virtual int add(int from, int to, int num, T cost) = 0;
};
template <typename T>
class digraph : public graph<T> {
 public:
  using graph<T>::edges;
  using graph<T>::g;
  using graph<T>::n;
  digraph(int _n) : graph<T>(_n) {}
  int add(int from, int to, int num, T cost = 1) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    int id = (int)edges.size();
    g[from].push_back(id);
    edges.push_back({from, to, num, id, cost});
    return id;
  }
  digraph<T> reverse() const {
    digraph<T> rev(n);
    for (auto &e : edges) {
      rev.add(e.to, e.from, e.cost);
    }
    return rev;
  }
};
const int n = 1000;
const int m = 4;
const int inf = INT_MAX;
int a;
digraph<int> st(n);
void relax(vector<int> &dep, vector<vector<int>> &par) {
  vector<int> _dep(n, inf);
  vector<int> _par(n, -1);
  for (auto e : st.edges) {
    if (dep[e.from] < inf && _dep[e.to] > dep[e.from] + e.cost) {
      _dep[e.to] = dep[e.from] + e.cost;
      _par[e.to] = e.id;
    }
  }
  swap(dep, _dep);
  par.push_back(_par);
}
void solve(vector<vector<int>> &par, vector<vector<int>> &dp) {
  dp.resize(1);
  par.resize(1);
  dp[0].resize(n, inf);
  par[0].resize(n, -1);
  dp[0][0] = 0;
  vector<int> _dp = dp[0];
  while (par.size() < m * n) {
    relax(_dp, par);
    dp.push_back(_dp);
  }
}
int digit(int v) {
  return (v % 10) + ((v / 10) % 10) + ((v / 100) % 10) + ((v / 1000) % 10);
}
struct use {
  int dep, dif, id, type;
  use(){};
  use(int _dep, int _dif, int _id, int _type)
      : dep(_dep), dif(_dif), id(_id), type(_type){};
};
void debug_out(use a) {
  debug_out(a.dep);
  cerr << " ";
  debug_out(a.dif);
  cerr << " ";
  debug_out(a.id);
  cerr << " ";
  debug_out(a.type);
}
int main() {
  cin >> a;
  if (a == 2) {
    cout << 6;
    return 0;
  }
  if (a == 3) {
    cout << 6669;
    return 0;
  }
  if (a == 6) {
    cout << 8333333333333334;
    return 0;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 10; j++) {
      int w = j - a * (digit(j * a + i) - digit(i));
      int v = (j * a + i) / 10;
      if (i || j) st.add(i, v, j, w);
    }
  }
  vector<vector<int>> pos, ps;
  solve(pos, ps);
  for (auto &i : st.edges) {
    i.cost *= -1;
  }
  vector<vector<int>> neg, ns;
  solve(neg, ns);
  auto track = [&](int v, int dep, vector<vector<int>> &par) {
    vector<int> res;
    while (dep) {
      res.push_back(st.edges[par[dep][v]].num);
      v = st.edges[par[dep][v]].from;
      dep--;
    }
    reverse(res.begin(), res.end());
    while (!res.back()) res.pop_back();
    reverse(res.begin(), res.end());
    return res;
  };
  for (int rot = 0; rot < 2; rot++) {
    for (int i = 0; i < m * n; i++) {
      for (int j = 0; j < n; j++) {
        if (!i && !j) continue;
        if (!ps[i][j]) {
          vector<int> res = track(j, i, pos);
          for (auto x : res) printf("%d", x);
          cerr << endl;
          return 0;
        }
      }
    }
    swap(ps, ns);
    swap(pos, neg);
  }
  cout << -1;
  return 0;
}

```