E. Decimal Expansion
time limit per test
1 second
memory limit per test
256 mebibytes
input
standard input
output
standard output

Consider the following constant: $$$$$$\varphi = \dfrac{9}{10} \cdot \dfrac{99}{100} \cdot \dfrac{999}{1000} \cdot \dfrac{9999}{10000}\cdot \dots$$$$$$

You have to find the $$$n$$$-th digit after the decimal separator in the decimal representation of $$$\varphi$$$.

Input

The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) which is the number of test cases.

The next line contains $$$t$$$ integers $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$), one for each test case.

Output

For each test case, output a single digit which is the answer to that test case. Separate consecutive answers by single spaces.

Example
Input
15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Output
8 9 0 0 1 0 0 9 9 9 9 8 9 9 9
Note

The constant evaluates as $$$\varphi = 0.890010099998999\dots$$$