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
def f(x): #including x
	dig, cnt = 1, 9
	ans = 0
	while dig != len(str(x)):
		ans += dig * cnt
		dig += 1
		cnt *= 10
	ans += (x - (cnt // 9) + 1) * dig
	return ans
k = int(input())
l, r = 1, 1000000000000
if k == 1:
    print(1)
    exit(0)
while l < r:
	mid = (l + r + 1) >> 1
	if f(mid) < k:
		l = mid
	else:
		r = mid - 1
k -= f(l)
l += 1
print(str(l)[k - 1])