诡计多端的Callisto

Callisto是一个诡计多端的人，他会随机的改变自己的行为方式为0或1。
Eruopa总结了一套Callisto行为方式的变化规律S。
S是一个下标从0开始的字符串，初始S为“0”，每次Eruopa会将S反转构造S'，反转指的是将0变成1，1变成0。接下来把S变成S+S'。下面给出S前几位的构造过程。

Eruopa想要知道现在Callisto是0还是1。

第一个行为正整数T($1 \le T \le 1000$)，表示测试例子的个数；
接下来每一行一个正整数n，表示下标($0 \le n \le 10^{18}$)。

对于每个测试例子，输出一行一个整数$S_n$。

2
0
3

0
0

$S_0=0, S_1=1, S_2=1, S_3=0, S_4=1, S_5=0, S_6=0, S_7=1$