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;
const long long mx = 1e18;
int n;
vector<long long> v;
long long a[25];
int main() {
  long long hgf = 1;
  a[1] = 1;
  for (int i = 2; i <= 17; ++i) {
    hgf *= 10;
    a[i] = hgf;
  }
  long long k = 90;
  long long sum = 9;
  v.push_back(0);
  v.push_back(9);
  for (int i = 2;; ++i) {
    sum += k * i;
    v.push_back(sum);
    if (sum >= 1688888888888888889ll) break;
    k = k * 10;
  }
  int t;
  long long p;
  scanf("%I64d", &p);
  int np = lower_bound(v.begin(), v.end(), p) - v.begin() - 1;
  long long rate = p - v[np];
  long long who = (rate + np) / (np + 1);
  long long ah = np + 1 - (rate + np) % (np + 1);
  long long ans = a[np + 1] + who - 1;
  for (int i = 1; i < ah; ++i) {
    ans /= 10;
  }
  printf("%I64d\n", ans % 10);
}
