[问题描述]

有一个无穷序列如下：110100100010000100000……

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

[输入]

第一行一个正整数N，表示询问次数；

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

[输出]

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

[输入样例]

4
3
14
7
6

[输出样例]

0
0
1
0

[数据范围]

对于100%数据有N<=1500000;Ai<=10^9