题目描述

$q$ 次询问，每次给一个正整数 $n$，问有多少个不超过 $n$ 的正整数 $i$ 使得 $i$ 和 $n\bmod i$ 都是质数。

输入格式

第一行一个正整数 $q$。

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

输出格式

$q$ 行，每行回答一组询问。

5
5
55
555
5555
55555

1
3
22
93
447

提示

本题采用捆绑测试。

数据范围：

• Subtask 1 (30pts)：$q=1$。
• Subtask 2 (70pts)：无特殊限制。

对于全部数据，$1\le n,q\le2\times10^5$。

洛谷代码长度限制：50 KB。