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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const long long Inf = 1e18;
const int mod = 1;
template <typename T = int>
T gi() {
  T x = 0, o = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
template <typename T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, 1 : 0;
};
template <typename T>
bool chkmin(T &a, T b) {
  return a > b ? a = b, 1 : 0;
};
int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
void inc(int &a, int b) { a = (a + b >= mod ? a + b - mod : a + b); }
void dec(int &a, int b) { a = (a - b < 0 ? a - b + mod : a - b); }
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + "," + to_string(p.second) + ")";
}
template <typename T>
string to_string(T v) {
  int fst = 1;
  string ret = "{";
  for (auto x : v) {
    if (!fst) ret += ",";
    fst = 0, ret += to_string(x);
  }
  ret += "}";
  return ret;
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  dbg_out(T...);
}
template <typename T>
int qpow(int a, T b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % mod;
    a = 1ll * a * a % mod, b >>= 1;
  }
  return ret;
}
int a;
const int lim = 2000;
bool vis[1010][lim << 1][2];
int f[1010][lim << 1][2];
tuple<int, int, int> pre[1010][lim << 1][2];
void print(int i, int j, int k, bool fl) {
  if (i == -1) return;
  if (f[i][j + lim][k] != 0) fl = 1;
  if (fl) printf("%d", f[i][j + lim][k]);
  int ii, jj, kk;
  tie(ii, jj, kk) = pre[i][j + lim][k];
  print(ii, jj, kk, fl);
}
void bfs() {
  vis[0][lim][1] = 1;
  queue<tuple<int, int, int>> q;
  q.push(make_tuple(0, 0, 1));
  pre[0][lim][1] = make_tuple(-1, -1, -1);
  while (!q.empty()) {
    int i, j, k;
    tie(i, j, k) = q.front();
    q.pop();
    if (!i && !j && !k) {
      print(i, j, k, 0);
      exit(0);
    }
    for (int c = 0; c <= 9; c++) {
      int ii, jj, kk;
      ii = (i + a * c) / 10, jj = j + a * ((i + a * c) % 10) - c,
      kk = k & (c == 0);
      if (abs(jj) > lim) continue;
      if (!vis[ii][jj + lim][kk]) {
        vis[ii][jj + lim][kk] = 1;
        pre[ii][jj + lim][kk] = make_tuple(i, j, k);
        f[ii][jj + lim][kk] = c;
        q.push(make_tuple(ii, jj, kk));
      }
    }
  }
}
int main() {
  a = gi();
  bfs();
  puts("-1");
  return 0;
}