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;
struct ako {
  int b2, c2, d;
  ako(int B = -1, int C = -1, int D = -1) : b2(B), c2(C), d(D) {}
};
const int minb = -2000, maxb = 4000, maxa = 1005;
ako vis[maxb - minb + 79][maxa];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a;
  cin >> a;
  queue<pair<int, int>> q;
  q.push({0, 0});
  while (!q.empty() && vis[-minb][0].d == -1) {
    int b = q.front().first, c = q.front().second;
    q.pop();
    for (int d = 0; d < 10; d++) {
      if (b == 0 && c == 0 && d == 0) continue;
      int nwb = b + a * ((c + a * d) % 10) - d, nwc = (c + a * d) / 10;
      if (minb > nwb || maxb < nwb || vis[nwb - minb][nwc].d != -1) continue;
      vis[nwb - minb][nwc] = ako(b, c, d);
      q.push({nwb, nwc});
    }
  }
  string ans;
  if (vis[-minb][0].d != -1) {
    int b = 0, c = 0;
    while (true) {
      ako k = vis[b - minb][c];
      if (!ans.empty() || k.d) ans.push_back('0' + k.d);
      if (k.b2 == 0 && k.c2 == 0) break;
      tie(b, c) = {k.b2, k.c2};
    }
  } else
    ans = "-1";
  cout << ans << endl;
  return 0;
}