Problem Description

把所有的二进制整数从小到大排在一起，会形成一个无限长的字符串 `s = "011011100101110111..."`，现在对于一个下标 `i`，你需要快速求出 `s[i]` 所对应的字符。

Input

第一行一个正整数 $T$ ($T\le10^5$) 表示数据组数。

接下来 $T$ 行，每行一个非负整数 $i$ ($i\le10^{18}$)，表示需要求出字符串对应位置上的字符。

Output

一共 $T$ 行，每行一个字符 `0` 或 `1` 表示字符串对应位置上的字符。

20
0
1
10
100
1000
10000
100000
1000000
10000000
100000000
1000000000
10000000000
100000000000
1000000000000
10000000000000
100000000000000
1000000000000000
10000000000000000
100000000000000000
1000000000000000000

0
1
0
1
0
0
1
1
1
0
0
0
1
0
1
1
1
0
0
0