Decimal Expansion
Time limit1sMemory limit512 MB
For each query n up to 10^18, find the n-th digit after the decimal point of the infinite product (9/10)(99/100)(999/1000)...
- Level
Hard9 of 10
- Topics
- Math, Number theory, Combinatorics, Implementation
- Solved
- No attempts yet
Problem
Consider the following constant:
[\phi = \frac{9}{10} \cdot \frac{99}{100} \cdot \frac{999}{1000} \cdot \frac{9999}{10000} \cdot \dots]
You have to find the n-th digit after the decimal point in the decimal representation of (\phi).
Input
The first line of input contains a single integer t (1 ≤ t ≤ 10^5), the number of test cases.
The next line contains t integers n (1 ≤ n ≤ 10^18), one for each test case.
Output
For each test case, output a single digit, the answer to that test case. Separate consecutive answers by single spaces.
Hint
The constant evaluates as (\phi) = 0.890010099998999...