无穷的序列

题目描述

有一个无穷序列如下： $110100100010000100000……$ 请你找出这个无穷序列中指定位置上的数字。

输入格式

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

输出格式

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

4 
3 
14 
7 
6

0
0
1
0

提示

对于 $100\%$ 的数据有 $N\le 1500000$，$A_i\le 10^9$

来源

童程童美