Consider an infinite string that consists of all positive integers in increasing order:

12345678910111213141516171819202122232425...

Your task is to process ~q~ queries of the form: what is the digit at position ~k~ in the string?

Input

• The first input line has an integer ~q~: the number of queries.

After this, there are ~q~ lines that describe the queries. Each line has an integer ~k~: a ~1~-indexed position in the string.

Output

• For each query, print the corresponding digit.

Constraints

• ~1 \le q \le 1000~
• ~1 \le k \le 10^{18}~

Example Input

3
7
19
12

Example Output

7
4
1