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;
long long int n, t, k;
vector<long long> a, b;
map<long long, long long> m;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  long long pro = 9;
  long long prepro = 0;
  long long a = 1, b = 1;
  while (n > pro) {
    prepro += 9 * a * b;
    a *= 10;
    b++;
    pro += 9 * a * b;
  }
  long long y = 0;
  for (long long i = 0; i < b - 1; i++) y = y * 10 + 1;
  y *= 9;
  y += (n - prepro + b - 1) / (b);
  long long x = (n - prepro) % (b);
  if (x == 0) x = b;
  vector<long long> v;
  while (y > 0) {
    v.push_back(y % 10);
    y /= 10;
  }
  reverse(v.begin(), v.end());
  cout << v[x - 1];
  return 0;
}
