Suppose you would write all successive natural numbers one after the other, starting with the number 1. This would give you an infinite series of digits, that starts as follows (for the sake of clarity we have put spaces in between numbers).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 …

We will not interpret this series as a series of numbers, but as a series of digits. The question that we then try to answer is what digit we will find on a given position $$n$$. From this example series, it is easy to verify that the sixteenth position holds the digit 1. But what is the digit that we find on position 2147483646 ?

Input

The first line of the input contains a number $$t$$ ($$1 \leq t \leq 1000$$) that specifies the number of tasks. After this, each of the $$t$$ tasks is described. A single task is described by a single line that contains the number $$k \in \mathbb{N}_0$$ ($$1 \leq k \leq 2^{31} - 1$$).

Output

For each task, write the $$k$$-th digit from the series of natural numbers that was described above.

Hint:If you try to generate the series of successive natural numbers with the aim to find the correct digit in it, this approach will be so slow that you'll exceed the time limit set for this programming task for large values of $$k$$. Try to find a better solution by making use of the observation that the first 9 natural numbers have a single digit, the next 90 natural number have two digits, the next 900 natural numbers have three digits, and so on.

Example

Input:

Output: