#include <bits/stdc++.h>
int A;
int gcd(int x, int y) {
  int r = 0;
  while (y) {
    r = x % y;
    x = y;
    y = r;
  }
  return x;
}
inline int four_digit(int x) {
  return x / 1000 + x / 100 % 10 + x / 10 % 10 + x % 10;
}
int Main() {
  if (A == 1) {
    puts("1");
    return 0;
  }
  if (A == 2) {
    puts("6");
    return 0;
  }
  if (A == 4) {
    puts("75");
    return 0;
  }
  if (A == 8) {
    puts("125");
    return 0;
  }
  int tmp = A;
  while (tmp % 2 == 0) tmp /= 2;
  while (tmp % 5 == 0) tmp /= 5;
  if (tmp == 1) {
    puts("-1");
    return 0;
  }
  for (int start = 1; start <= 100000; start++) {
    static char q[10000000];
    int r = 0, San = 0, Sn = 0, leading_zero = 0, L = 0;
    for (int i = 1; i <= 1000 * A; i++) {
      int next = i == 1 ? start : 0;
      San += next;
      int cur = (r * 10 + next) / A;
      Sn += cur;
      if (cur) leading_zero = 1;
      if (leading_zero) q[L++] = cur + 48;
      r = (r * 10 + next) % A;
      for (int j = (A - r * 10000 % A) % A; j < 10000; j += A) {
        int Tan = j, Tn = (r * 10000 + j) / A;
        int Aan = San + four_digit(Tan);
        int An = Sn + four_digit(Tn);
        if (Aan * A == An) {
          q[L] = 0;
          printf("%s", q);
          if (leading_zero)
            printf("%04d\n", Tn);
          else
            printf("%d\n", Tn);
          return 0;
        }
      }
    }
  }
  return 0;
}
int main() {
  scanf("%d", &A);
  Main();
  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>
int A;
int gcd(int x, int y) {
  int r = 0;
  while (y) {
    r = x % y;
    x = y;
    y = r;
  }
  return x;
}
inline int four_digit(int x) {
  return x / 1000 + x / 100 % 10 + x / 10 % 10 + x % 10;
}
int Main() {
  if (A == 1) {
    puts("1");
    return 0;
  }
  if (A == 2) {
    puts("6");
    return 0;
  }
  if (A == 4) {
    puts("75");
    return 0;
  }
  if (A == 8) {
    puts("125");
    return 0;
  }
  int tmp = A;
  while (tmp % 2 == 0) tmp /= 2;
  while (tmp % 5 == 0) tmp /= 5;
  if (tmp == 1) {
    puts("-1");
    return 0;
  }
  for (int start = 1; start <= 100000; start++) {
    static char q[10000000];
    int r = 0, San = 0, Sn = 0, leading_zero = 0, L = 0;
    for (int i = 1; i <= 1000 * A; i++) {
      int next = i == 1 ? start : 0;
      San += next;
      int cur = (r * 10 + next) / A;
      Sn += cur;
      if (cur) leading_zero = 1;
      if (leading_zero) q[L++] = cur + 48;
      r = (r * 10 + next) % A;
      for (int j = (A - r * 10000 % A) % A; j < 10000; j += A) {
        int Tan = j, Tn = (r * 10000 + j) / A;
        int Aan = San + four_digit(Tan);
        int An = Sn + four_digit(Tn);
        if (Aan * A == An) {
          q[L] = 0;
          printf("%s", q);
          if (leading_zero)
            printf("%04d\n", Tn);
          else
            printf("%d\n", Tn);
          return 0;
        }
      }
    }
  }
  return 0;
}
int main() {
  scanf("%d", &A);
  Main();
  return 0;
}

```