题目描述 q 次询问，每次给一个正整数 n，问有多少个不超过 n 的正整数 i 使得 i 和 n mod i 都是质数。

输入格式
第一行一个正整数 q。

后 q 行，每行一个正整数 n。

输出格式 n 行，每行回答一组询问。

输入输出样例 输入
5
5
55
555
5555
55555
输出 #1复制
1
3
22
93
447
说明/提示
本题采用捆绑测试。

数据范围：

Subtask 1 (30pts)： ?

1 q=1。 Subtask 2 (70pts)：无特殊限制。 对于全部数据， 1 ≤ ? , ? ≤ 2 × 1 0 5 1≤n,q≤2×10 5 。