题目描述

奥特曼正在和小怪兽进行激烈的战斗。奥特曼有一系列攻击模式，其中每个攻击模式的威力按照某种规律生成，变成了一个无穷序列如下：
110100100010000100000…
你需要帮助奥特曼找出这个无穷攻击序列中指定位置上的攻击威力。

输入格式：

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

输出格式：

N行，每行为0或l，表示序列第Ai位上的攻击威力。

输入样例#1：

4
3
14
7
6 

输出样例#1：

0
0
1
0

数据范围：

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