题目描述

有一个无穷序列如下：

110100100010000100000…

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

输入格式

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

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

输出格式

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

4
3
14
7
6 

0
0
1
0

提示

对于100%的数据有N≤1500000，Ai≤10^9