P11419 [Sloi 2024]D1T3 pi(n)
题目背景
很多年前，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$ 的值。
说明/提示
**本题采用捆绑测试**
| 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}$。