题目背景

很多年前，zydy 突发奇想：只要算出 $\pi(n)\bmod2，\pi(n)\bmod3，\pi(n)\bmod5，···$，就能得到 $\pi(n)$。很多年后，zydy 才意识到这其实是可行的，现在你只需要帮助他算出 $\pi(n)\bmod2$。

题目描述

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

输入格式

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

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

输出格式

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

3
1000
1000000
1000000000

0
0
0

1
23571113171923

1

提示

本题采用捆绑测试 | 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}$。