### 问题描述 一共 $t$ 次询问，每次询问给定一个正整数 $N$，你需要计算满足条件 $p^2q + q^2p \le N$，且 $p,q$ 均为素数的不同的二元组 $(p, q)$ 一共有多少对？ 注意二元组是有序的，若 $p \neq q$，那么 $(p, q)$ 和 $(q, p)$ 是不同的二元组，而若 $p = q$ ，$(p, q)$ 和 $(q,p)$ 是相同的二元组。 ### 输入格式 输入第 $1$ 行包含一个整数 $t$，表示询问的次数。 第 $2 \sim {t + 1}$ 行每行包括一个正整数 $N$，其含义如上所述。 ### 输出格式 对于每次询问输出一行，包含一个整数表示对于这次询问满足条件的二元组的数量。 ### 样例输入 ```text 2 100 998244353 ``` ### 样例输出 ```text 6 78622 ``` ### 说明 对于样例中的第一次询问，$N = 100$ 时有以下 $6$ 种情况： $p = 2, q = 2, p^2q + q^2p = 16$ $p = 2, q = 3, p^2q + q^2p = 30$ $p = 2, q = 5, p^2q + q^2p = 70$ $p = 3, q = 2, p^2q + q^2p = 30$ $p = 3, q = 3, p^2q + q^2p = 54$ $p = 5, q = 2, p^2q + q^2p = 70$ 可以证明，不存在其它的二元组 $(p, q)$ 满足题目中条件。 ### 评测数据规模 对于 $20\%$ 的评测数据，$1 \le N \le 500$。 另有 $20\%$ 的评测数据，$t = 1$。 对于所有评测数据，$1 \le t \le 40$，$1 \le N \le 10^{16}$。