#include <bits/stdc++.h>
using namespace std;
class abc {
  long long int *a;
  long long n;

 public:
  void inp() {
    cin >> n;
    a = new long long[10001];
    a[0] = 19;
    long long int i = 20;
    long long int count = 1;
    while (count < 10001) {
      long long int sum = 0, temp;
      long long int div = 10;
      temp = i;
      while (temp > 0) {
        sum = sum + (temp % div);
        temp = temp / div;
      }
      if (sum == 10) {
        a[count++] = i;
      }
      i++;
    }
    cout << a[n - 1];
  }
};
int main() {
  abc *a;
  long long int t;
  t = 1;
  a = new abc[t];
  for (long long int i = 0; i < t; i++) {
    long long int p1 = 0;
    a[i].inp();
  }
  return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

We consider a positive integer perfect, if and only if the sum of its digits is exactly 10. Given a positive integer k, your task is to find the k-th smallest perfect positive integer.

Input

A single line with a positive integer k (1 ≤ k ≤ 10 000).

Output

A single number, denoting the k-th smallest perfect integer.

Examples

Input

1


Output

19


Input

2


Output

28

Note

The first perfect integer is 19 and the second one is 28.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
class abc {
  long long int *a;
  long long n;

 public:
  void inp() {
    cin >> n;
    a = new long long[10001];
    a[0] = 19;
    long long int i = 20;
    long long int count = 1;
    while (count < 10001) {
      long long int sum = 0, temp;
      long long int div = 10;
      temp = i;
      while (temp > 0) {
        sum = sum + (temp % div);
        temp = temp / div;
      }
      if (sum == 10) {
        a[count++] = i;
      }
      i++;
    }
    cout << a[n - 1];
  }
};
int main() {
  abc *a;
  long long int t;
  t = 1;
  a = new abc[t];
  for (long long int i = 0; i < t; i++) {
    long long int p1 = 0;
    a[i].inp();
  }
  return 0;
}

```