#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
const int BUFFER_SIZE = 1 << 18;
const int INF = 1 << 30;
const long long LINF = 1ll << 60;
char BUFFER[BUFFER_SIZE];
int gi() {
  int x;
  scanf("%d", &x);
  return x;
}
double gd() {
  double x;
  scanf("%lf", &x);
  return x;
}
vector<int> gvi(int n) {
  vector<int> a;
  while (n--) a.push_back(gi());
  return a;
}
string gs() {
  scanf("%s", BUFFER);
  return string(BUFFER);
}
istringstream buff() { return istringstream(string(BUFFER)); }
template <class T>
struct forArray {
  T* a;
  int n;
  forArray(T* a, int n) : a(a), n(n) {}
};
template <class A, class B>
ostream& operator<<(ostream& os, const pair<A, B>& d);
template <class T>
ostream& operator<<(ostream& os, const vector<T>& d);
template <class T>
ostream& operator<<(ostream& os, const queue<T>& d);
template <class T>
ostream& operator<<(ostream& os, const stack<T>& d);
template <class T>
ostream& operator<<(ostream& os, const set<T>& d);
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& d);
template <class T>
ostream& operator<<(ostream& os, const unordered_set<T>& d);
template <class A, class B>
ostream& operator<<(ostream& os, const map<A, B>& d);
template <class A, class B>
ostream& operator<<(ostream& os, const multimap<A, B>& d);
template <class A, class B>
ostream& operator<<(ostream& os, const unordered_map<A, B>& d);
template <class T>
ostream& operator<<(ostream& os, const vector<T>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class T>
ostream& operator<<(ostream& os, const queue<T>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class T>
ostream& operator<<(ostream& os, const stack<T>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class T>
ostream& operator<<(ostream& os, const set<T>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class T>
ostream& operator<<(ostream& os, const unordered_set<T>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class A, class B>
ostream& operator<<(ostream& os, const map<A, B>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class A, class B>
ostream& operator<<(ostream& os, const multimap<A, B>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class A, class B>
ostream& operator<<(ostream& os, const unordered_map<A, B>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class T>
ostream& operator<<(ostream& os, const forArray<T>& d) {
  os << "[";
  for (int i = 0; i < d.n; ++i) {
    if (i) os << ",";
    os << d.a[i];
  }
  return os << "]";
}
template <class A, class B>
ostream& operator<<(ostream& os, const pair<A, B>& d) {
  return os << "[" << d.first << ", " << d.second << "]";
}
int MID = 1500;
int D[3000][1000];
pair<int, int> P[3000][1000];
int Pd[3000][1000];
pair<int, int> Q[3000 * 1000 + 100];
string solve3(int A) {
  memset((D), (-1), sizeof(D));
  D[MID][0] = 0;
  int qw = 0;
  Q[qw++] = {0, 0};
  for (int q = 0; q < qw; ++q) {
    int b = Q[q].first;
    int x = Q[q].second;
    for (int d = q ? 0 : 1; d < 10; ++d) {
      int v = x * 10 + d;
      int bb = b + A * d - v / A;
      int xx = v % A;
      if (bb + MID < 0 || bb + MID >= 3000) continue;
      if (bb == 0 && xx == 0) {
        string s = "";
        s += d + '0';
        while (b || x) {
          int bbb = P[MID + b][x].first;
          int xxx = P[MID + b][x].second;
          s += '0' + Pd[MID + b][x];
          b = bbb;
          x = xxx;
        }
        reverse((s).begin(), (s).end());
        string r = "";
        int m = 0;
        for (char c : s) {
          m = m * 10 + (c - '0');
          if (m / A || r.size()) {
            r += '0' + (m / A);
          }
          m %= A;
        }
        return r;
      }
      if (D[bb + MID][xx] == -1) {
        D[bb + MID][xx] = D[b + MID][x] + 1;
        Q[qw++] = {bb, xx};
        P[bb + MID][xx] = {b, x};
        Pd[bb + MID][xx] = d;
      }
    }
  }
  return "-1";
}
int main() {
  string s = solve3(gi());
  printf("%s\n", s.c_str());
  return 0;
}

### Prompt

Your task is to create a CPP solution 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 double eps = 1e-9;
const int BUFFER_SIZE = 1 << 18;
const int INF = 1 << 30;
const long long LINF = 1ll << 60;
char BUFFER[BUFFER_SIZE];
int gi() {
  int x;
  scanf("%d", &x);
  return x;
}
double gd() {
  double x;
  scanf("%lf", &x);
  return x;
}
vector<int> gvi(int n) {
  vector<int> a;
  while (n--) a.push_back(gi());
  return a;
}
string gs() {
  scanf("%s", BUFFER);
  return string(BUFFER);
}
istringstream buff() { return istringstream(string(BUFFER)); }
template <class T>
struct forArray {
  T* a;
  int n;
  forArray(T* a, int n) : a(a), n(n) {}
};
template <class A, class B>
ostream& operator<<(ostream& os, const pair<A, B>& d);
template <class T>
ostream& operator<<(ostream& os, const vector<T>& d);
template <class T>
ostream& operator<<(ostream& os, const queue<T>& d);
template <class T>
ostream& operator<<(ostream& os, const stack<T>& d);
template <class T>
ostream& operator<<(ostream& os, const set<T>& d);
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& d);
template <class T>
ostream& operator<<(ostream& os, const unordered_set<T>& d);
template <class A, class B>
ostream& operator<<(ostream& os, const map<A, B>& d);
template <class A, class B>
ostream& operator<<(ostream& os, const multimap<A, B>& d);
template <class A, class B>
ostream& operator<<(ostream& os, const unordered_map<A, B>& d);
template <class T>
ostream& operator<<(ostream& os, const vector<T>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class T>
ostream& operator<<(ostream& os, const queue<T>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class T>
ostream& operator<<(ostream& os, const stack<T>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class T>
ostream& operator<<(ostream& os, const set<T>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class T>
ostream& operator<<(ostream& os, const unordered_set<T>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class A, class B>
ostream& operator<<(ostream& os, const map<A, B>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class A, class B>
ostream& operator<<(ostream& os, const multimap<A, B>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class A, class B>
ostream& operator<<(ostream& os, const unordered_map<A, B>& d) {
  os << "[";
  int f = 0;
  for (auto x : d) {
    if (f) os << ",";
    f = 1;
    os << x;
  }
  return os << "]";
};
template <class T>
ostream& operator<<(ostream& os, const forArray<T>& d) {
  os << "[";
  for (int i = 0; i < d.n; ++i) {
    if (i) os << ",";
    os << d.a[i];
  }
  return os << "]";
}
template <class A, class B>
ostream& operator<<(ostream& os, const pair<A, B>& d) {
  return os << "[" << d.first << ", " << d.second << "]";
}
int MID = 1500;
int D[3000][1000];
pair<int, int> P[3000][1000];
int Pd[3000][1000];
pair<int, int> Q[3000 * 1000 + 100];
string solve3(int A) {
  memset((D), (-1), sizeof(D));
  D[MID][0] = 0;
  int qw = 0;
  Q[qw++] = {0, 0};
  for (int q = 0; q < qw; ++q) {
    int b = Q[q].first;
    int x = Q[q].second;
    for (int d = q ? 0 : 1; d < 10; ++d) {
      int v = x * 10 + d;
      int bb = b + A * d - v / A;
      int xx = v % A;
      if (bb + MID < 0 || bb + MID >= 3000) continue;
      if (bb == 0 && xx == 0) {
        string s = "";
        s += d + '0';
        while (b || x) {
          int bbb = P[MID + b][x].first;
          int xxx = P[MID + b][x].second;
          s += '0' + Pd[MID + b][x];
          b = bbb;
          x = xxx;
        }
        reverse((s).begin(), (s).end());
        string r = "";
        int m = 0;
        for (char c : s) {
          m = m * 10 + (c - '0');
          if (m / A || r.size()) {
            r += '0' + (m / A);
          }
          m %= A;
        }
        return r;
      }
      if (D[bb + MID][xx] == -1) {
        D[bb + MID][xx] = D[b + MID][x] + 1;
        Q[qw++] = {bb, xx};
        P[bb + MID][xx] = {b, x};
        Pd[bb + MID][xx] = d;
      }
    }
  }
  return "-1";
}
int main() {
  string s = solve3(gi());
  printf("%s\n", s.c_str());
  return 0;
}

```