题目描述：

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

输入格式：

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

输出格式：

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

样例：

4 
3 
14 
7 
6

0
0
1
0

提示

对于 100% 的数据有 $N≤150000，Ai≤10^8$