时间限制： 2.0 秒

空间限制： 256 MB

题目背景

没有人在热河路谈恋爱，

总有人在天亮时伤感

如果年轻时你没来过热河路，

那你现在的生活是不是很幸福

——李志《热河》

奔跑。跌倒。奔跑。

题目描述

热河路有一家开了好多年的理发店，不管剪什么样的发型，你只要付五块钱。现在我们来到了热河路。

我们可以将其抽象成一个如下的序列：

110100100010000100000......

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

输入格式

从标准输入读入数据。

第一行一个正整数 $n~(1\le n\le 1.5\times 10^6)$，表示询问次数。

接下来的 $n$ 行，每行一个正整数 $a_{i}$ ($1 \leq a_{i} \leq 10^{9}$)，$a_{i}$ 表示在序列中的位置。

输出格式

输出到标准输出。

输出 $n$ 行，每行为一个 $0$ 或 $1$，表示该序列第 $a_{i}$ 位上的数字。

4
3
14
7
6

0
0
1
0

提示

本题输入输出量较大，请采用效率较高的输入输出方式。