思路

• 一个数恰有三个因子当且仅当它是某个素数的平方：$n = p^2$。

  • 若 $n=p^2$，其因子为 $1,p,p^2$ 共 $3$ 个。
  • 若有恰好 $3$ 个因子，则其素因子分解必须是 $p^2$ 的形式。

• 因此，区间 $[l,r]$ 内伪质数的个数等于满足 $p^2 \in [l,r]$ 的素数 $p$ 的个数。

• 令 $A=\lfloor \sqrt{r} \rfloor$，$B=\lfloor \sqrt{l-1} \rfloor$，答案为

题目内容

众所周知，质数是指大于 $1$ 且只有 $1$ 及其本身 两个因子的数。

Tk 学习质数后对这种特殊数产生极大的兴趣；

Tk 定义 伪质数 为一个大于 $1$ 并且恰有三个不同正因子的整数；

现在，给定一个闭区间 $[l,r]$ ，Tk 想知道区间中伪质数的个数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^4)$ 代表数据组数；

此后每组测试数据描述如下：

在一行上输入两个整数 $l,r(1≤l≤r≤ 10^{14})$ ，表示询问区间的左右端点。

输出描述

对于每一组测试数据，新起一行。

输出一个整数，表示区间内伪质数的个数。

样例1

输入

2
1 10
13 15

输出

2
0