Description

There is a sequence $A$ with infinitely many elements, $A_i=\overline{1\underbrace{000\dots0}_{i-1\text{ 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$.

Input Format

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 Format

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

4
3
14
7
6 

0
0
1
0

Hint

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

Translated by ChatGPT 5