Description

Define the function $\mathrm{tostring}(n)$ as writing the number $n$ in base $10$ as a string. For example, $\mathrm{tostring}(12345)={\tt 12345}$. Based on this,

• Define the string $S_n={\tt 1+2+3+4+\cdots}+\mathrm{tostring}(n)$.
• Define the string $S_{\infty}=S_1+S_2+S_3+S_4+\cdots$.

For example, the beginning of $S_{\infty}$ is:

$$\tt 112123123412345123456123456712345678123456789123456789101234567891011\cdots$$

Now, for a given $i$, determine the character at position $i$ of $S_{\infty}$.

Input Format

The first line contains a positive integer $t\ (1 \le t \le 10)$, the number of testcases.

The next $t$ lines each contain one positive integer $i\ (1 \le i \le 2^{31}-1)$, representing a query.

Output Format

For each $i$, output the digit at the corresponding position.

2
3
8

2
2

Hint

Translated by ChatGPT 5