there is an infinite string that consists of all positive integers (increasing order)

12345678910111213141516171819202122232425......

Now you have Q queries ask about what is the digit at position k in the string ?

Input Format

first line Q

next Q lines have an integer k

Constraints

1q1000

1k10^18

Output Format

the digit at position k in the string

Sample Input 0

3 7 19 12 

Sample Output 0

7 4 1

in c++ or python