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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
inline char gc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long read() {
  long long x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') positive = 0;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
inline void write(long long a) {
  if (a < 0) {
    a = -a;
    putchar('-');
  }
  if (a >= 10) write(a / 10);
  putchar('0' + a % 10);
}
inline void writeln(long long a) {
  write(a);
  puts("");
}
inline void wri(long long a) {
  write(a);
  putchar(' ');
}
const int M = 5005;
bool vis[1005][M << 1];
int fr[1005][M << 1][3];
int main() {
  int a = read();
  queue<pair<int, int> > q;
  q.push(make_pair(0, M));
  while (q.size()) {
    int dq = q.front().first, cha = q.front().second;
    q.pop();
    for (int i = dq == 0 && cha == M; i < 10; i++) {
      int xdq = (dq + i * a) / 10, dig = (dq + i * a) % 10;
      int xcha = cha + i - dig * a;
      if (xcha < 0 || xcha >= 2 * M) continue;
      if (vis[xdq][xcha]) continue;
      vis[xdq][xcha] = 1;
      fr[xdq][xcha][0] = dq;
      fr[xdq][xcha][1] = cha;
      fr[xdq][xcha][2] = i;
      q.push(make_pair(xdq, xcha));
    }
  }
  if (!vis[0][M]) {
    puts("-1");
    return 0;
  }
  int x = 0, y = M;
  vector<int> ans;
  while (1) {
    ans.push_back(fr[x][y][2]);
    int nx = fr[x][y][0];
    y = fr[x][y][1];
    x = nx;
    if (x == 0 && y == M) break;
  }
  reverse(ans.begin(), ans.end());
  while (ans.size() && *ans.rbegin() == 0) ans.pop_back();
  reverse(ans.begin(), ans.end());
  for (auto i : ans) write(i);
}