#include <bits/stdc++.h>
using namespace std;
int gi() {
  int x = 0, w = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') w = 0, ch = getchar();
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  return w ? x : -x;
}
const int N = 2005;
int a, n, vis[N][N << 1], s[N * N];
pair<pair<int, int>, int> pre[N][N << 1];
queue<pair<int, int> > Q;
void add(int x, int y, int z) {
  int nx = (x + z * a) / 10, ny = y + (x + z * a) % 10 * a - z;
  if (ny <= -N || ny >= N || vis[nx][ny + N]) return;
  Q.push(make_pair(nx, ny));
  vis[nx][ny + N] = 1;
  pre[nx][ny + N] = make_pair(make_pair(x, y), z);
}
int main() {
  a = gi();
  for (int i = 1; i < 10; ++i) add(0, 0, i);
  while (!Q.empty()) {
    int x = Q.front().first, y = Q.front().second;
    Q.pop();
    if (x == 0 && y == 0)
      while (233) {
        s[n++] = pre[x][y + N].second;
        int px = pre[x][y + N].first.first, py = pre[x][y + N].first.second;
        if (px == 0 && py == 0) {
          int p = 0;
          while (!s[p]) ++p;
          while (p < n) putchar(s[p] + '0'), ++p;
          return 0;
        }
        x = px, y = py;
      }
    for (int z = 0; z < 10; ++z) add(x, y, z);
  }
  puts("-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;
int gi() {
  int x = 0, w = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') w = 0, ch = getchar();
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
  return w ? x : -x;
}
const int N = 2005;
int a, n, vis[N][N << 1], s[N * N];
pair<pair<int, int>, int> pre[N][N << 1];
queue<pair<int, int> > Q;
void add(int x, int y, int z) {
  int nx = (x + z * a) / 10, ny = y + (x + z * a) % 10 * a - z;
  if (ny <= -N || ny >= N || vis[nx][ny + N]) return;
  Q.push(make_pair(nx, ny));
  vis[nx][ny + N] = 1;
  pre[nx][ny + N] = make_pair(make_pair(x, y), z);
}
int main() {
  a = gi();
  for (int i = 1; i < 10; ++i) add(0, 0, i);
  while (!Q.empty()) {
    int x = Q.front().first, y = Q.front().second;
    Q.pop();
    if (x == 0 && y == 0)
      while (233) {
        s[n++] = pre[x][y + N].second;
        int px = pre[x][y + N].first.first, py = pre[x][y + N].first.second;
        if (px == 0 && py == 0) {
          int p = 0;
          while (!s[p]) ++p;
          while (p < n) putchar(s[p] + '0'), ++p;
          return 0;
        }
        x = px, y = py;
      }
    for (int z = 0; z < 10; ++z) add(x, y, z);
  }
  puts("-1");
  return 0;
}

```