该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

T-质数（tprime）

【题目描述】

如果一个数恰好有 $3$ 个正约数，那么这个数称为 T-质数。

现在给出 $T$ 组询问，每组询问给出一个区间 $[l, r]$，问区间中有多少个 T-质数。

【输入格式】

第一行一个整数 $T$，表示询问组数。

接下来 $T$ 行，每行两个整数 $l, r$，表示询问的区间。

【输出格式】

输出 $T$ 行，每行一个整数，表示对应询问的答案。

【样例输入】

3
1 10
1 100
1 1000000

【样例输出】

2
4
78498

【样例解释】

对于样例1，在 $2,3,4,5,6,7,8,9,10$ 中，只有 $4$ 和 $9$ 是 T-质数，所以答案为 $2$。

【数据范围及约定】

对于 $100\%$ 的数据，$T \le 10^5$，$1 \le l \le r \le 10^{12}$。