#include <bits/stdc++.h>
using namespace std;
const int N = 1005, magic = 4005;
bitset<2 * magic> vis[N];
tuple<short, short, short> par[N][2 * magic];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int a;
  cin >> a;
  queue<int> que;
  que.push(0);
  que.push(magic);
  while (que.size() > 0) {
    int carry = que.front();
    que.pop();
    int balance = que.front();
    que.pop();
    int low = 0;
    if (carry == 0 && balance == magic) low = 1;
    for (int d = low; d < 10; d++) {
      int ncarry = (carry + d * a) / 10;
      int nbalance = balance - d + ((carry + d * a) % 10) * a;
      if (nbalance >= 0 && nbalance < 2 * magic && !vis[ncarry][nbalance]) {
        vis[ncarry][nbalance] = true;
        par[ncarry][nbalance] = make_tuple(carry, balance, d);
        que.push(ncarry);
        que.push(nbalance);
      }
    }
  }
  if (!vis[0][magic])
    cout << "-1" << endl;
  else {
    string res;
    int carry = 0, balance = magic;
    while (true) {
      auto t = par[carry][balance];
      res.push_back(get<2>(t) + '0');
      carry = get<0>(t);
      balance = get<1>(t);
      if (carry == 0 && balance == magic) break;
    }
    while (res.back() == '0') res.pop_back();
    reverse(res.begin(), res.end());
    while (res.back() == '0') res.pop_back();
    reverse(res.begin(), res.end());
    cout << res << endl;
  }
  return 0;
}

### Prompt

Please create a solution in Cpp to the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1005, magic = 4005;
bitset<2 * magic> vis[N];
tuple<short, short, short> par[N][2 * magic];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int a;
  cin >> a;
  queue<int> que;
  que.push(0);
  que.push(magic);
  while (que.size() > 0) {
    int carry = que.front();
    que.pop();
    int balance = que.front();
    que.pop();
    int low = 0;
    if (carry == 0 && balance == magic) low = 1;
    for (int d = low; d < 10; d++) {
      int ncarry = (carry + d * a) / 10;
      int nbalance = balance - d + ((carry + d * a) % 10) * a;
      if (nbalance >= 0 && nbalance < 2 * magic && !vis[ncarry][nbalance]) {
        vis[ncarry][nbalance] = true;
        par[ncarry][nbalance] = make_tuple(carry, balance, d);
        que.push(ncarry);
        que.push(nbalance);
      }
    }
  }
  if (!vis[0][magic])
    cout << "-1" << endl;
  else {
    string res;
    int carry = 0, balance = magic;
    while (true) {
      auto t = par[carry][balance];
      res.push_back(get<2>(t) + '0');
      carry = get<0>(t);
      balance = get<1>(t);
      if (carry == 0 && balance == magic) break;
    }
    while (res.back() == '0') res.pop_back();
    reverse(res.begin(), res.end());
    while (res.back() == '0') res.pop_back();
    reverse(res.begin(), res.end());
    cout << res << endl;
  }
  return 0;
}

```