P1795 无穷的序列

有一个序列 $A$，元素为无穷多，$A_i=\overline{1\underbrace{000\dots0}_{i-1 \text{ 个 }0}}$。有另一个无穷序列 $B$，$B=\overline{\underbrace{A_1A_2A_3A_4\dots}_{\text{第 i 个为 }A_i}}$，其中 $\overline{xy}$ 代表把 $x$ 和 $y$ 拼接在一起，更多数字同理。 这样，无穷序列 $B$ 的前若干项表示为：$\texttt{110100100010000100000}\dots$ 请你找出无穷序列 $B$ 中指定位置上的数字。

第一行一个正整数 $N$ ，表示询问次数； 接下来的 $N$ 行每行一个正整数 $a_i$，$a_i$ 表示在序列中的位置。

输出为 $N$ 行，每行为 $0$ 或 $1$ ，表示序列第 $a_i$ 位上的数字。

对于 $100\%$ 的数据，$N \leq 1\,500\,000$，$a_i\le 10^9$。