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, k, i = 0, r, m, j;
  cin >> n;
  long long int a[14], b[14];
  a[0] = 0;
  b[0] = 0;
  for (i = 1; i < 13; i++) {
    a[i] = 9 * pow(10, i - 1);
    b[i] = a[i] * i + b[i - 1];
  }
  i = 0;
  while (b[i] < n) i++;
  k = (n - b[i - 1]) / i;
  r = (n - b[i - 1]) % i;
  m = pow(10, i - 1) - 1 + k;
  if (r == 0) {
    cout << m % 10;
    return 0;
  }
  m++;
  j = i - r;
  while (j--) m /= 10;
  cout << m % 10;
  return 0;
}
