Description

有一个无穷序列如下：110100100010000100000… 请你找出这个无穷序列中指定位置上的数字

Format

Input

第一行一个正整数 N，表示询问次数；接下来的 N 行每行一个正整数 Ai，Ai 表示在序列中的位置。

Output

N 行，每行为 0 或 1，表示序列第 Ai 位上的数字。

Samples

4
3
14
7
6

0
O
1
0

Limitation

对于 l00％的数据有 N≤1500000，Ai≤10^9