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 dp[14][2][2][14];
vector<int> v;
void make(long long x) {
  v.clear();
  while (x) {
    v.push_back(x % 10);
    x /= 10;
  }
  if (v.size() == 0) v.push_back(0);
  reverse(v.begin(), v.end());
}
long long f(int i, int smaller, int zero, int tot) {
  if (i == v.size()) {
    return tot;
  }
  if (dp[i][smaller][zero][tot] != -1) return dp[i][smaller][zero][tot];
  long long value = 0;
  int lim = v[i];
  if (smaller) lim = 9;
  for (int j = 0; j <= lim; j++) {
    if (j < lim) {
      if (j == 0) {
        if (zero == 1)
          value += f(i + 1, 1, 1, tot + 1);
        else
          value += f(i + 1, 1, 0, tot);
      } else {
        value += f(i + 1, 1, 1, tot + 1);
      }
    } else {
      if (j == 0) {
        if (zero == 1)
          value += f(i + 1, smaller, 1, tot + 1);
        else
          value += f(i + 1, smaller, 0, tot);
      } else {
        value += f(i + 1, smaller, 1, tot + 1);
      }
    }
  }
  return dp[i][smaller][zero][tot] = value;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long k;
  cin >> k;
  long long hi = k, low = 0, mid, t = 100, ans = -1;
  while (t--) {
    mid = (hi + low) / 2;
    make(mid);
    memset(dp, -1, sizeof(dp));
    long long temp = f(0, 0, 0, 0);
    if (temp < k) {
      ans = mid;
      low = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  make(ans);
  memset(dp, -1, sizeof(dp));
  long long temp = f(0, 0, 0, 0);
  ans++;
  make(ans);
  for (int i = 0; i < v.size(); i++) {
    temp++;
    if (temp == k) {
      cout << v[i] << endl;
      break;
    }
  }
  return 0;
}
