20001 - Semi-prime H-numbers

注意题目相比原题有改动

H 数是指那些比 k 的倍数多 1 的正整数，当k=4时，1, 5, 9, 13, 17, 21, ... 都是 H 数。在本题中，我们假定这些就是全部的数。H 数集在乘法下是封闭的。

与常规整数类似，我们将 H 数划分为单位、H 素数和 H 合数。1 是唯一的单位。一个 H 数 h 被称为 H 素数，如果它不是单位，并且只能表示为两个 H 数的乘积：1×h。其余的数则称为 H 合数。

例如，当我们取k为4的时候，前几个 H 合数有：5×5=25，5×9=45，5×13=65，9×9=81，5×17=85。

你的任务是统计 H 半素数的个数。H 半素数是指恰好可以表示为两个 H 素数乘积的 H 数，这两个 H 素数可以相等也可以不同。在上面的例子中，所有五个数都是 H 半素数。而 125=5×5×5 不是 H 半素数，因为它是三个 H 素数的乘积。

第一行输入k和T，表示H数的性质是比k倍多1的正整数,T是测试的样例组数 接下来的每一行输入一个n，表示一次对1 \sim n的查询

对于每一个输入的n，输出一行表示1\sim n之间的半质数个数，两者之间用空格分隔，格式如样例所示

对于100\%的数据 T\leq 1000,1\leq k < n 其中90 \%的数据k^2 < n

对于25\%的数据，n \leq 10^2

对于50\%的数据，n \leq 10^3

对于75\%的数据，n \leq 10^4

对于100\%的数据，n \leq 10^6

一本通