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;
const int N = 3005;
int hd, tl, sta[N][N], dig[N][N];
pair<int, int> q[N * 1500], pre[N][N], tt;
inline string solve(int A) {
  memset(sta, -1, sizeof(sta));
  sta[0][((0) + 1500)] = 0;
  q[hd = tl = 1] = pair<int, int>(0, 0);
  while (hd <= tl) {
    int car = q[hd].first, bal = q[hd].second;
    for (register int tmp, ncar, nbal, num = hd > 1 ? 0 : 1; num < 10; ++num) {
      tmp = car * 10 + num;
      ncar = tmp % A;
      nbal = bal + A * num - tmp / A;
      if (((nbal) + 1500) > 3000 || ((nbal) + 1500) < 0) continue;
      if (!nbal && !ncar) {
        string ret = "", tret = "";
        tret += (char)(num ^ 48);
        while (car || bal) {
          tret += (char)(dig[car][((bal) + 1500)] ^ 48);
          tt = pre[car][((bal) + 1500)];
          car = tt.first, bal = tt.second;
        }
        reverse(tret.begin(), tret.end());
        for (register int sum = 0, i = 0, up = tret.size(); i ^ up; ++i) {
          sum = sum * 10 + (tret[i] ^ 48);
          if (sum / A || ret.size()) ret += (char)((sum / A) ^ 48);
          sum %= A;
        }
        return ret;
      }
      if (sta[ncar][((nbal) + 1500)] == -1) {
        sta[ncar][((nbal) + 1500)] = sta[car][((bal) + 1500)] + 1;
        q[++tl] = pair<int, int>(ncar, nbal);
        pre[ncar][((nbal) + 1500)] = pair<int, int>(car, bal);
        dig[ncar][((nbal) + 1500)] = num;
      }
    }
    ++hd;
  }
  return "-1";
}
int main() {
  int A;
  scanf("%d", &A);
  cout << solve(A);
  return 0;
}