#include <bits/stdc++.h>
using namespace std;
int poss[1000][10], diff[1000][10];
pair<pair<int, int>, int> parent[1000][20000];
queue<pair<int, int> > Q;
int main() {
  int a;
  cin >> a;
  int i, j;
  for (i = 0; i < a; i++) {
    for (j = 0; j < 10; j++) {
      int l = (a * j + i) % 10, c = (a * j + i) / 10;
      poss[i][j] = c, diff[i][j] = a * l - j;
    }
  }
  for (i = 0; i < a; i++) {
    for (j = 0; j < 20000; j++) parent[i][j] = make_pair(make_pair(-1, -1), -1);
  }
  for (i = 1; i < 10; i++) {
    parent[poss[0][i]][diff[0][i] + 2000] = make_pair(make_pair(-1, -1), i);
    Q.push(make_pair(poss[0][i], diff[0][i]));
  }
  while (!Q.empty()) {
    pair<int, int> u = Q.front();
    Q.pop();
    if (u == make_pair(0, 0)) break;
    for (i = 0; i < 10; i++) {
      int c = poss[u.first][i];
      int d = u.second + diff[u.first][i];
      if ((d >= -2000) && (d < 4000) && (parent[c][d + 2000].second == -1)) {
        parent[c][d + 2000] = make_pair(u, i);
        Q.push(make_pair(c, d));
      }
    }
  }
  if (parent[0][2000].second == -1)
    printf("-1\n");
  else {
    vector<int> ans;
    pair<int, int> u = make_pair(0, 0);
    while (parent[u.first][u.second + 2000].first.first != -1) {
      int d = parent[u.first][u.second + 2000].second;
      if (!ans.empty() || (d > 0)) ans.push_back(d);
      u = parent[u.first][u.second + 2000].first;
    }
    ans.push_back(parent[u.first][u.second + 2000].second);
    for (i = 0; i < ans.size(); i++) printf("%d", ans[i]);
    printf("\n");
  }
  while (!Q.empty()) Q.pop();
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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 poss[1000][10], diff[1000][10];
pair<pair<int, int>, int> parent[1000][20000];
queue<pair<int, int> > Q;
int main() {
  int a;
  cin >> a;
  int i, j;
  for (i = 0; i < a; i++) {
    for (j = 0; j < 10; j++) {
      int l = (a * j + i) % 10, c = (a * j + i) / 10;
      poss[i][j] = c, diff[i][j] = a * l - j;
    }
  }
  for (i = 0; i < a; i++) {
    for (j = 0; j < 20000; j++) parent[i][j] = make_pair(make_pair(-1, -1), -1);
  }
  for (i = 1; i < 10; i++) {
    parent[poss[0][i]][diff[0][i] + 2000] = make_pair(make_pair(-1, -1), i);
    Q.push(make_pair(poss[0][i], diff[0][i]));
  }
  while (!Q.empty()) {
    pair<int, int> u = Q.front();
    Q.pop();
    if (u == make_pair(0, 0)) break;
    for (i = 0; i < 10; i++) {
      int c = poss[u.first][i];
      int d = u.second + diff[u.first][i];
      if ((d >= -2000) && (d < 4000) && (parent[c][d + 2000].second == -1)) {
        parent[c][d + 2000] = make_pair(u, i);
        Q.push(make_pair(c, d));
      }
    }
  }
  if (parent[0][2000].second == -1)
    printf("-1\n");
  else {
    vector<int> ans;
    pair<int, int> u = make_pair(0, 0);
    while (parent[u.first][u.second + 2000].first.first != -1) {
      int d = parent[u.first][u.second + 2000].second;
      if (!ans.empty() || (d > 0)) ans.push_back(d);
      u = parent[u.first][u.second + 2000].first;
    }
    ans.push_back(parent[u.first][u.second + 2000].second);
    for (i = 0; i < ans.size(); i++) printf("%d", ans[i]);
    printf("\n");
  }
  while (!Q.empty()) Q.pop();
  return 0;
}

```