#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int INF = 1e9 + 7;
const double eps = 1e-6;
const int MAXN = 1e6 + 7;
vector<long long> res;
int main() {
  for (int x1 = 0; x1 <= 9; x1++) {
    int sum1 = x1, p1 = x1;
    for (int x2 = 0; x2 <= 9; x2++) {
      if (p1 + x2 > 10) break;
      int p2 = p1 + x2, sum2 = sum1 * 10 + x2;
      for (int x3 = 0; x3 <= 9; x3++) {
        if (p2 + x3 > 10) break;
        int p3 = p2 + x3, sum3 = sum2 * 10 + x3;
        for (int x4 = 0; x4 <= 9; x4++) {
          if (p3 + x4 > 10) break;
          int p4 = p3 + x4, sum4 = sum3 * 10 + x4;
          for (int x5 = 0; x5 <= 9; x5++) {
            if (p4 + x5 > 10) break;
            int p5 = p4 + x5, sum5 = sum4 * 10 + x5;
            for (int x6 = 0; x6 <= 9; x6++) {
              if (p5 + x6 > 10) break;
              int p6 = p5 + x6, sum6 = sum5 * 10 + x6;
              for (int x7 = 0; x7 <= 9; x7++) {
                if (p6 + x7 > 10) break;
                int p7 = p6 + x7, sum7 = sum6 * 10 + x7;
                for (int x8 = 0; x8 <= 9; x8++) {
                  if (p7 + x8 > 10) break;
                  int p8 = p7 + x8, sum8 = sum7 * 10 + x8;
                  if (p8 == 10) res.push_back(sum8);
                }
              }
            }
          }
        }
      }
    }
  }
  int n;
  cin >> n;
  cout << res[n - 1] << endl;
  return 0;
}

### Prompt

Your task is to create a CPP solution 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>
#pragma GCC optimize(2)
using namespace std;
const int INF = 1e9 + 7;
const double eps = 1e-6;
const int MAXN = 1e6 + 7;
vector<long long> res;
int main() {
  for (int x1 = 0; x1 <= 9; x1++) {
    int sum1 = x1, p1 = x1;
    for (int x2 = 0; x2 <= 9; x2++) {
      if (p1 + x2 > 10) break;
      int p2 = p1 + x2, sum2 = sum1 * 10 + x2;
      for (int x3 = 0; x3 <= 9; x3++) {
        if (p2 + x3 > 10) break;
        int p3 = p2 + x3, sum3 = sum2 * 10 + x3;
        for (int x4 = 0; x4 <= 9; x4++) {
          if (p3 + x4 > 10) break;
          int p4 = p3 + x4, sum4 = sum3 * 10 + x4;
          for (int x5 = 0; x5 <= 9; x5++) {
            if (p4 + x5 > 10) break;
            int p5 = p4 + x5, sum5 = sum4 * 10 + x5;
            for (int x6 = 0; x6 <= 9; x6++) {
              if (p5 + x6 > 10) break;
              int p6 = p5 + x6, sum6 = sum5 * 10 + x6;
              for (int x7 = 0; x7 <= 9; x7++) {
                if (p6 + x7 > 10) break;
                int p7 = p6 + x7, sum7 = sum6 * 10 + x7;
                for (int x8 = 0; x8 <= 9; x8++) {
                  if (p7 + x8 > 10) break;
                  int p8 = p7 + x8, sum8 = sum7 * 10 + x8;
                  if (p8 == 10) res.push_back(sum8);
                }
              }
            }
          }
        }
      }
    }
  }
  int n;
  cin >> n;
  cout << res[n - 1] << endl;
  return 0;
}

```