406314: GYM102354 E Decimal Expansion

Memory Limit:0 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Decimal Expansiontime limit per test1 secondmemory limit per test256 mebibytesinputstandard inputoutputstandard 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.

ExampleInput
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$$$

加入题单

上一题 下一题 算法标签: