#P1795. 无穷的序列

无穷的序列

题目描述

有一个无穷序列如下:

110100100010000100000\texttt{110100100010000100000}

请你找出这个无穷序列中指定位置上的数字。

输入格式

第一行一个正整数 NN ,表示询问次数;

接下来的 NN 行每行一个正整数 AiA_iAiA_i 表示在序列中的位置。

输出格式

输出为 NN 行,每行为 00ll ,表示序列第 AiA_i 位上的数字。

4
3
14
7
6 

0
0
1
0

提示

对于 100%100\% 的数据,N1500000N \leq 1\,500\,000Ai109A_i≤10^9