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 MAX_A = 1e3, REM_NEG = 1e3, REM_POS = 1e3;
int dp[REM_NEG + REM_POS + 1][MAX_A];
int A;
int prerem[REM_NEG + REM_POS + 1][MAX_A], prekuri[REM_NEG + REM_POS + 1][MAX_A];
int main() {
  scanf("%d", &A);
  memset(dp, -1, sizeof(dp));
  queue<pair<int, int> > que;
  que.push(pair<int, int>(0, 0));
  bool flg = false;
  while (!que.empty()) {
    pair<int, int> p = que.front();
    que.pop();
    for (int i = (0); i < (10); i++) {
      if (i > 0 || flg) {
        int nxtrem, nxtkuri;
        int tp = p.second + i * A;
        nxtrem = p.first + tp % 10 * A - i;
        nxtkuri = tp / 10;
        if (-REM_NEG <= nxtrem && nxtrem <= REM_POS &&
            dp[nxtrem + REM_NEG][nxtkuri] == -1) {
          prerem[nxtrem + REM_NEG][nxtkuri] = p.first;
          prekuri[nxtrem + REM_NEG][nxtkuri] = p.second;
          dp[nxtrem + REM_NEG][nxtkuri] = i;
          que.push(pair<int, int>(nxtrem, nxtkuri));
        }
      }
    }
    flg = true;
  }
  if (dp[REM_NEG][0] != -1) {
    deque<int> ans;
    flg = false;
    for (int rem = 0, kuri = 0; rem != 0 || kuri > 0 || !flg;) {
      ans.push_back(dp[rem + REM_NEG][kuri]);
      int rem2 = prerem[rem + REM_NEG][kuri],
          kuri2 = prekuri[rem + REM_NEG][kuri];
      rem = rem2;
      kuri = kuri2;
      flg = true;
    }
    while (ans.front() == 0) ans.pop_front();
    for (auto v : ans) {
      printf("%d", v);
    }
    printf("\n");
  } else {
    printf("-1\n");
  }
}