题目背景

Nick是一位精通分裂与合成的炼金术士，可以将一个金块完美地复制成两个，也可以完美地合成一个，且保证大小不变。

熟练掌握这项技能的Nick正百无聊赖地盯着一地的金块，他决定研发一个游戏来打发下时间。

题目描述

Nick拿出了无限多个坩埚，并把它们排成一排。每个坩埚里可以放无限多块金块，也可以不放金块。

最开始，Nick在某个坩埚里放了一块金块，并且把它取名为 $0$号坩埚。接下来的每一个时刻，Nick都决定做如下两个操作中的一个。

（1）若坩埚 $i$ 中有金块，那Nick将在坩埚 $i$ 中拿出一块金块并把它炼化成两块，各放到与它相邻的坩埚 $i-1$ 和 $i+1$ 里。

（2）若坩埚 $i-1$ 和 $i+1$ 里都有金块，那Nick将两坩埚中各取出一块金块，将两块金块聚合成一块金块之后放在 $i$ 坩埚里。

现在Nick想要问你，经过足够长的时间后，是否能让这排坩埚里只有编号为 $x$ 的坩埚里有且仅有一块金块。(只有坩埚 $x$ 内有仅一块金块，并且除坩埚 $x$ 外其他格子内没有金块)

但Nick非常的任性，没有告诉你他在哪个时刻对哪个坩埚里的哪块金块进行了哪个操作。

输入格式

本题含有多组数据。

第一行一个整数 T，表示数据组数。

后面，每一行输入一个整数 $x$，代表询问的坩埚编号。

输出格式

一行一个整数表示对应输入行的答案。

如果能满足题意，那么输出 $1$，否则输出 $0$。

7
48
26
8
12
31
2
47

1
0
0
1
0
0
0

提示

对题面描述的各操作的解释如下

在初始时刻在某一坩埚内放入一块金块，并将此坩埚标号为 $0$。

在下一个时刻可对于 $0$ 号坩埚做分裂操作，位于 $0$ 坩埚中的一块金块被分裂成两块，分别被放在 $-1,1$ 号坩埚中。

在下一个时刻可对于 $-1,1$ 号坩埚做聚合操作，分别位于这两个坩埚中的一块金块会被聚合成一块，并被放在 $0$ 号坩埚中。

当然你也可以在刚才对 $-1$ 号坩埚的金块做分裂操作，于是这时 $-2,0,1$ 号坩埚有金块。

数据范围

$-10^{100}\le x \le10^{100}$。

询问最多只有 $5000$ 组。