#include <bits/stdc++.h>
using namespace std;
queue<pair<int, int> > q;
pair<int, int> fa[2010][4010];
int num[2010][4010], a;
bool vis[2010][4010];
inline int rd() {
  int x = 0;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    ;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  return x;
}
inline void trans(int x, int y, int z) {
  int xx = (x + z * a) / 10, yy = y + (x + z * a) % 10 * a - z;
  if (abs(yy) > 2000) return;
  if (!vis[xx][yy + 2000])
    vis[xx][yy + 2000] = true, fa[xx][yy + 2000] = pair<int, int>(x, y),
                 num[xx][yy + 2000] = z, q.push(pair<int, int>(xx, yy));
}
inline void trans1(int x, int y, int z) {
  int xx = (x + z * a) / 10, yy = y + (x + z * a) % 10 * a - z;
  if (abs(yy) > 2000) return;
  if (!vis[xx][yy + 2000])
    vis[xx][yy + 2000] = true, fa[xx][yy + 2000] = pair<int, int>(-1, -1),
                 num[xx][yy + 2000] = z, q.push(pair<int, int>(xx, yy));
}
bool flag = false;
inline void print(pair<int, int> hh) {
  if (hh.first < 0) return;
  if (num[hh.first][hh.second + 2000]) flag = true;
  if (flag) putchar(num[hh.first][hh.second + 2000] + '0');
  print(fa[hh.first][hh.second + 2000]);
}
int main() {
  a = rd();
  for (int i = 1; i < 10; i++) trans1(0, 0, i);
  while (!q.empty()) {
    pair<int, int> hh = q.front();
    q.pop();
    if (!hh.first && !hh.second) {
      print(hh);
      putchar('\n');
      return 0;
    }
    for (int i = 0; i < 10; i++) trans(hh.first, hh.second, i);
  }
  puts("-1");
  return 0;
}

### Prompt

Your challenge is to write 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;
queue<pair<int, int> > q;
pair<int, int> fa[2010][4010];
int num[2010][4010], a;
bool vis[2010][4010];
inline int rd() {
  int x = 0;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    ;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  return x;
}
inline void trans(int x, int y, int z) {
  int xx = (x + z * a) / 10, yy = y + (x + z * a) % 10 * a - z;
  if (abs(yy) > 2000) return;
  if (!vis[xx][yy + 2000])
    vis[xx][yy + 2000] = true, fa[xx][yy + 2000] = pair<int, int>(x, y),
                 num[xx][yy + 2000] = z, q.push(pair<int, int>(xx, yy));
}
inline void trans1(int x, int y, int z) {
  int xx = (x + z * a) / 10, yy = y + (x + z * a) % 10 * a - z;
  if (abs(yy) > 2000) return;
  if (!vis[xx][yy + 2000])
    vis[xx][yy + 2000] = true, fa[xx][yy + 2000] = pair<int, int>(-1, -1),
                 num[xx][yy + 2000] = z, q.push(pair<int, int>(xx, yy));
}
bool flag = false;
inline void print(pair<int, int> hh) {
  if (hh.first < 0) return;
  if (num[hh.first][hh.second + 2000]) flag = true;
  if (flag) putchar(num[hh.first][hh.second + 2000] + '0');
  print(fa[hh.first][hh.second + 2000]);
}
int main() {
  a = rd();
  for (int i = 1; i < 10; i++) trans1(0, 0, i);
  while (!q.empty()) {
    pair<int, int> hh = q.front();
    q.pop();
    if (!hh.first && !hh.second) {
      print(hh);
      putchar('\n');
      return 0;
    }
    for (int i = 0; i < 10; i++) trans(hh.first, hh.second, i);
  }
  puts("-1");
  return 0;
}

```