Description

定义 $\pi(n)$ 为不大于 $n$ 的素数的个数，给定 $n$，计算 $\pi(n)\bmod 2$ 。

Input Format

输入第一行 $T$，表示数据组数。

以下 $T$ 行，每行一个正整数 $n$。

Output Format

输出 $T$ 行，每行一个非负整数，为 $\pi(n)\bmod 2$ 的值。

3
1000
1000000
1000000000

0
0
0

1
23571113171923

1

Hint

本题采用捆绑测试 | Subtask | T | n | Score | | :----------: | :----------: | :----------: | :----------: | | $1$ | $=1000$ | $\le 10^8$ | $20$ | | $2$ | $=10$ | $\le 10^{11}$ | $20$ | | $3$ | $=10$ | $\le 10^{13}$ | $20$ | | $4$ | $=5$ | $\le 10^{15}$ | $20$ | | $5$ | $=5$ | $\le 10^{16}$ | $20$ |

对 $100\%$ 的数据，$T\le 1000$，$1\le n\le 10^{16}$。