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

\(12345678910111213141516171819202122232425\ldots\)

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 \leq q \leq 1000\)
• \(1 \leq k \leq 10^{18}\)

Example

Sample input

3  
7  
19  
12

Sample output

7  
4  
1