P1795 Infinite Sequence

There is a sequence $A$ with infinitely many elements, $A_i=\overline{1\underbrace{000\dots0}_{\text{$i-1$ zeros}}}$. There is another infinite sequence $B$, $B=\overline{\underbrace{A_1A_2A_3A_4\dots}_{\text{the }i\text{-th is }A_i}}$, where $\overline{xy}$ denotes concatenating $x$ and $y$, and similarly for more numbers. Thus, the first several digits of the infinite sequence $B$ are: $\texttt{110100100010000100000}\dots$. Please find the digit at the specified position in the infinite sequence $B$.

The first line contains a positive integer $N$, the number of queries. Each of the next $N$ lines contains a positive integer $a_i$, where $a_i$ denotes a position in sequence $B$.

Output $N$ lines, each being $0$ or $1$, representing the digit at position $a_i$ in the sequence.

For $100\%$ of the testdata, $N \leq 1\,500\,000$, $a_i \le 10^9$. Translated by ChatGPT 5