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;
using namespace std::chrono;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  auto start = high_resolution_clock::now();
  vector<pair<long long, long long> > res;
  long long sum = 0;
  long long n = 1;
  res.push_back({0, 0});
  while (sum <= 1e12) {
    sum += (9 * pow(10, n - 1) * n);
    long long p = pow(10, n) - 1;
    res.push_back({sum, p});
    n++;
  }
  long long k;
  cin >> k;
  long long num;
  for (long long i = 0; i < res.size(); i++) {
    if (k <= res[i].first) {
      num = (k - res[i - 1].first - 1) / (i) + 1 + res[i - 1].second;
      long long rem = (k - res[i - 1].first - 1) % (i);
      long long ct = 0;
      for (long long i = num; i > 0; i = i / 10) {
        ct++;
      }
      rem = ct - rem;
      long long pt = 1;
      for (long long i = num; i > 0; i = i / 10) {
        if (pt == rem) {
          cout << i % 10;
          return 0;
        }
        pt++;
      }
    }
  }
  auto stop = high_resolution_clock::now();
  auto duration = duration_cast<microseconds>(stop - start);
}
