#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5, mod = 998244353, M = 5e3 + 5;
template <class o>
inline void qr(o &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + (c ^ 48);
    c = getchar();
  }
  x *= f;
}
template <class o>
void qw(o x) {
  if (x / 10) qw(x / 10);
  putchar(x % 10 + 48);
}
template <class o>
void pr1(o x) {
  if (x < 0) putchar('-'), x = -x;
  qw(x);
  putchar(' ');
}
template <class o>
void pr2(o x) {
  if (x < 0) putchar('-'), x = -x;
  qw(x);
  puts("");
}
inline int ksm(int a, int b = mod - 2) {
  int ans = 1;
  for (; b; b >>= 1, a = 1ll * a * a % mod)
    if (b & 1) ans = 1ll * ans * a % mod;
  return ans;
}
inline int add(int a, int b) { return a += b, a >= mod ? a - mod : a; }
inline int sub(int a, int b) { return a -= b, a < 0 ? a + mod : a; }
bool vis[1005][M << 1];
pair<int, int> q[1005 * M * 2];
int p[1005][M << 1];
char ans[500005];
void solve() {
  int a;
  qr(a);
  int l = 1, r = 0;
  q[++r] = make_pair(0, M);
  while (l <= r) {
    int x = q[l].first, y = q[l++].second;
    for (int dig = 0; dig <= 9; ++dig) {
      if (l == 2 && !dig) continue;
      int nx = (x + dig * a) / 10;
      int ny = y + dig - (x + dig * a) % 10 * a;
      if (ny < 0 || ny >= 2 * M || vis[nx][ny]) continue;
      vis[nx][ny] = 1;
      q[++r] = make_pair(nx, ny);
      p[nx][ny] = y * 11000 + x * 10 + dig;
    }
  }
  if (!vis[0][M]) {
    puts("-1");
    return;
  }
  int x = 0, y = M, len = 0;
  for (;;) {
    int py = p[x][y] / 11000;
    int px = p[x][y] % 11000 / 10;
    ans[++len] = p[x][y] % 10 + '0';
    x = px, y = py;
    if (!x && y == M) break;
  }
  int p = 1;
  for (; ans[p] == '0'; ++p)
    ;
  printf("%s\n", ans + p);
}
int main() {
  solve();
  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;
const int N = 3e5 + 5, mod = 998244353, M = 5e3 + 5;
template <class o>
inline void qr(o &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + (c ^ 48);
    c = getchar();
  }
  x *= f;
}
template <class o>
void qw(o x) {
  if (x / 10) qw(x / 10);
  putchar(x % 10 + 48);
}
template <class o>
void pr1(o x) {
  if (x < 0) putchar('-'), x = -x;
  qw(x);
  putchar(' ');
}
template <class o>
void pr2(o x) {
  if (x < 0) putchar('-'), x = -x;
  qw(x);
  puts("");
}
inline int ksm(int a, int b = mod - 2) {
  int ans = 1;
  for (; b; b >>= 1, a = 1ll * a * a % mod)
    if (b & 1) ans = 1ll * ans * a % mod;
  return ans;
}
inline int add(int a, int b) { return a += b, a >= mod ? a - mod : a; }
inline int sub(int a, int b) { return a -= b, a < 0 ? a + mod : a; }
bool vis[1005][M << 1];
pair<int, int> q[1005 * M * 2];
int p[1005][M << 1];
char ans[500005];
void solve() {
  int a;
  qr(a);
  int l = 1, r = 0;
  q[++r] = make_pair(0, M);
  while (l <= r) {
    int x = q[l].first, y = q[l++].second;
    for (int dig = 0; dig <= 9; ++dig) {
      if (l == 2 && !dig) continue;
      int nx = (x + dig * a) / 10;
      int ny = y + dig - (x + dig * a) % 10 * a;
      if (ny < 0 || ny >= 2 * M || vis[nx][ny]) continue;
      vis[nx][ny] = 1;
      q[++r] = make_pair(nx, ny);
      p[nx][ny] = y * 11000 + x * 10 + dig;
    }
  }
  if (!vis[0][M]) {
    puts("-1");
    return;
  }
  int x = 0, y = M, len = 0;
  for (;;) {
    int py = p[x][y] / 11000;
    int px = p[x][y] % 11000 / 10;
    ans[++len] = p[x][y] % 10 + '0';
    x = px, y = py;
    if (!x && y == M) break;
  }
  int p = 1;
  for (; ans[p] == '0'; ++p)
    ;
  printf("%s\n", ans + p);
}
int main() {
  solve();
  return 0;
}

```