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
import java.util.*;

public class Solution {

    public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
       int itrIdx = 0;
       int itr = 0;
       int num = 0;
       while(itrIdx < n){
           itrIdx += (itr+1)*(Math.pow(10,itr+1) - Math.pow(10,itr));
           num+= (Math.pow(10,itr+1) - Math.pow(10,itr));
           itr++;
       }

        itrIdx -= itr*(Math.pow(10,itr)-Math.pow(10,itr-1));
        num -= (Math.pow(10,itr)-Math.pow(10,itr-1));
        int lastNum = num + ((n-itrIdx)/itr);
        int lastNumIndex = itrIdx + (itr* (lastNum-num));

        if(lastNumIndex == n){
            lastNumIndex = lastNumIndex-itr;
            lastNum -=1;
        }

        String nextNum = String.valueOf(lastNum+=1);
        System.out.println(nextNum.charAt(n-lastNumIndex-1));

    }
}


