题目描述

考虑这样一个序列 "110100100010000……" ，就是 "1"+"10"+"100"+"1000"+... 要求求出第 i 位是 0 还是 1 。

输入格式

第一行： N ，测试点的个数 ( 0 < N < 10000 )

第二行： N 个数( 每个数>0 ) ，每个数均不超过 $10^4$

输出格式

对每个测试点输出 0 或 1 ，每行一个数。

样例

3
1 2 3

1
1
0