#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= f;
}
template <class T>
inline void umin(T &x, T y) {
  x = x < y ? x : y;
}
template <class T>
inline void umax(T &x, T y) {
  x = x > y ? x : y;
}
inline unsigned int R() {
  static unsigned int seed = 416;
  return seed ^= seed >> 5, seed ^= seed << 17, seed ^= seed >> 13;
}
const int N = 1020;
int a, pre[N][N * 2];
pair<int, int> b[N][N * 2];
pair<int, int> q[N * N * 2];
int main() {
  read(a);
  memset(pre, -1, sizeof(pre));
  int f = 0, r = 1;
  q[f] = pair<int, int>(0, N);
  while (f != r) {
    pair<int, int> s = q[f++];
    int x = s.first, y = s.second;
    for (register int i = (0); i <= (9); i++) {
      int nx = (x + i * a) / 10, ny = y + i - (x + i * a) % 10 * a;
      if (ny > 0 && ny < N * 2 && !(x == 0 && y == N && i == 0) &&
          pre[nx][ny] == -1) {
        pre[nx][ny] = i;
        b[nx][ny] = s;
        q[r++] = pair<int, int>(nx, ny);
      }
    }
  }
  if (pre[0][N] == -1) {
    puts("-1");
    return 0;
  }
  int x = 0, y = N;
  bool ok = 0;
  while (1) {
    if (pre[x][y]) ok = 1;
    if (ok) printf("%d", pre[x][y]);
    pair<int, int> s = b[x][y];
    x = s.first;
    y = s.second;
    if (x == 0 && y == N) break;
  }
  return 0;
}

### Prompt

Your task is to create a CPP solution to 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 <class T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= f;
}
template <class T>
inline void umin(T &x, T y) {
  x = x < y ? x : y;
}
template <class T>
inline void umax(T &x, T y) {
  x = x > y ? x : y;
}
inline unsigned int R() {
  static unsigned int seed = 416;
  return seed ^= seed >> 5, seed ^= seed << 17, seed ^= seed >> 13;
}
const int N = 1020;
int a, pre[N][N * 2];
pair<int, int> b[N][N * 2];
pair<int, int> q[N * N * 2];
int main() {
  read(a);
  memset(pre, -1, sizeof(pre));
  int f = 0, r = 1;
  q[f] = pair<int, int>(0, N);
  while (f != r) {
    pair<int, int> s = q[f++];
    int x = s.first, y = s.second;
    for (register int i = (0); i <= (9); i++) {
      int nx = (x + i * a) / 10, ny = y + i - (x + i * a) % 10 * a;
      if (ny > 0 && ny < N * 2 && !(x == 0 && y == N && i == 0) &&
          pre[nx][ny] == -1) {
        pre[nx][ny] = i;
        b[nx][ny] = s;
        q[r++] = pair<int, int>(nx, ny);
      }
    }
  }
  if (pre[0][N] == -1) {
    puts("-1");
    return 0;
  }
  int x = 0, y = N;
  bool ok = 0;
  while (1) {
    if (pre[x][y]) ok = 1;
    if (ok) printf("%d", pre[x][y]);
    pair<int, int> s = b[x][y];
    x = s.first;
    y = s.second;
    if (x == 0 && y == N) break;
  }
  return 0;
}

```