# 无穷的序列

## 题目描述

有一个无穷序列如下：

$\texttt{110100100010000100000}$…

请你找出这个无穷序列中指定位置上的数字。

## 输入格式

第一行一个正整数 $N$ ，表示询问次数；

接下来的 $N$ 行每行一个正整数 $A_i$，$A_i$ 表示在序列中的位置。

## 输出格式

输出为 $N$ 行，每行为 $0$ 或 $1$ ，表示序列第  $A_i$ 位上的数字。

## 样例 #1

### 样例输入 #1

```
4
3
14
7
6
```

### 样例输出 #1

```
0
0
1
0
```

## 提示

对于 $100\%$ 的数据，$N \leq 1\,500\,000$，$A_i≤10^9$。