Let's write all the positive integer numbers one after another from 1 without any delimiters (i.e. as a single string). It will be the infinite sequence starting with 123456789101112131415161718192021222324252627282930313233343536...

Your task is to print the k-th digit of this sequence.

Input

The first and only line contains integer k (1 ≤ k ≤ 10000) — the position to process (1-based index).

Output

Print the k-th digit of the resulting infinite sequence.

Examples

Input


7


Output


7


Input


21


Output


5
#include <bits/stdc++.h>
using namespace std;
int main() {
  long long int n;
  long long int d = 0, temp = 0;
  cin >> n;
  if (n < 10) cout << n;
  if (n > 9 && n <= 189) {
    if ((n - 9) % 2 == 0)
      cout << (9 + (n - 9) / 2) % 10;
    else
      cout << (10 + (n - 9) / 2) / 10;
  }
  if (n > 189 && n <= 2889) {
    n = n - 189;
    if (n % 3 == 0)
      cout << (99 + (n / 3)) % 10;
    else {
      temp = n % 3;
      n = 100 + n / 3;
      if (temp == 1) temp = temp + 2;
      while (temp > 0) {
        d = n % 10;
        n = n / 10;
        temp--;
      }
      cout << d;
    }
  }
  if (n > 2889 && n <= 10000) {
    n = n - 2889;
    if (n % 4 == 0)
      cout << (999 + (n / 4)) % 10;
    else {
      temp = n % 4;
      n = 1000 + n / 4;
      switch (temp) {
        case 1:
          temp = temp + 3;
          break;
        case 2:
          temp = temp + 1;
          break;
        default:
          temp = temp - 1;
      }
      while (temp > 0) {
        d = n % 10;
        n = n / 10;
        temp--;
      }
      cout << d;
    }
  }
}
