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 = (int)1123, mod = (int)1e9 + 7, inf = (int)1e9;
const long long INF = (long long)1e18;
int a, ca[N][2 * N], ansa, ansb;
pair<int, int> v[N][2 * N];
bool used[N][2 * N];
vector<int> ansv;
queue<pair<int, int> > q;
int main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(NULL);
  cin >> a;
  used[0][a] = 1;
  q.push(make_pair(0, 0));
  int n = 0;
  while (!q.empty()) {
    n++;
    int x = q.front().first, y = q.front().second;
    q.pop();
    for (int c = 0; c < 10; ++c) {
      if (c == 0 && x == 0 && y == 0) continue;
      int xa = (x + a * c) / 10, ya = y + a * ((x + a * c) % 10) - c;
      if (abs(ya) > a) continue;
      if (xa == 0 && ya == 0) {
        ansa = x, ansb = y;
        break;
      }
      if (!used[xa][ya + a]) {
        used[xa][ya + a] = 1;
        v[xa][ya + a] = make_pair(x, y);
        ca[xa][ya + a] = c;
        q.push(make_pair(xa, ya));
      }
    }
  }
  while (ansa != 0 || ansb != 0) {
    ansv.push_back(ca[ansa][ansb + a]);
    pair<int, int> pr = v[ansa][ansb + a];
    ansa = pr.first, ansb = pr.second;
  }
  if (ansv.size() == 0) ansv.push_back(-1);
  reverse(ansv.begin(), ansv.end());
  while (ansv.size() > 0 && ansv.back() == 0) ansv.pop_back();
  reverse(ansv.begin(), ansv.end());
  for (int i : ansv) cout << i;
  return 0;
}