**Time limit:**1.00 s**Memory limit:**512 MB

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

Output:

7 4 1