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 get1(n):
    res = 0
    st = 1
    while st <= n:
        res += len(str(st))
        st += 1
    return res

def get(n):
    if n == 0:
        return 0
    
    L = len(str(n))
    res = 0
    prev = 1
    for i in range(1, L):
        res += i * ((10**i) - prev)
        prev = (10**i)
     
    res += (n - 10**(L - 1) + 1) * L

    return res

def solve(n):
    start = 1
    end = 10**18
    it = 70
    while it:
        it -= 1
        mid = (start + end) / 2
        if get(mid) >= n:
            end = mid
        else:
            start = mid
    
    for i in range(mid - 5, mid + 5):
        if i >= 1:
            cur = str(i)
            s = ''
            for j in cur:
                s += j
                if get(i - 1) + len(s) == n:
                    return j
    return mid

n = input()
X = solve(n)
print X