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>
int main() {
  int n, i, a[10000], j, t, c = 0, d, p, g, b, q, r[10];
  for (i = 1, j = 1; i <= 10000; i++) {
    if (i >= 1 && i <= 9) {
      a[i] = j;
      j = j + 1;
    } else if (i <= 99) {
      a[i] = j;
      j = j + 2;
    } else if (i <= 999) {
      a[i] = j;
      j = j + 3;
    } else if (i <= 9999) {
      a[i] = j;
      j = j + 4;
    } else if (i == 10000) {
      a[i] = j;
    }
  }
  scanf("%d", &n);
  for (i = 1; i <= 10000; i++) {
    if (a[i] > n) {
      t = i - 1;
      break;
    }
  }
  p = t;
  d = n - a[t];
  while (p != 0) {
    p = p / 10;
    c++;
  }
  i = c - 1;
  while (t != 0) {
    r[i] = t % 10;
    t = t / 10;
    i--;
  }
  printf("%d\n", r[d]);
  return 0;
}
