题目内容

对于正整数 $n$，记 $d(n)$ 为 $n$ 的不同正因子个数。如果 $d(n)$ 是一个素数，则称 $n$ 为一个「星数」。

现在给出 $T$ 个闭区间 $[l, r]$，你需要计算每个区间内有多少个星数。

测试数据组数 $T$ 不超过 $10^4$，所有 $l$ 和 $r$ 满足 $1 \le l \le r \le 2 \times 10^9$。

输入描述

第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示询问的组数。接下来 $T$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le 2 \times 10^9$），表示一个闭区间。

输出描述

对于每组测试数据，输出一行一个整数，表示区间 $[l, r]$ 内星数的个数。

样例1

输入

3
1 2
4 8
16 25

输出

1
3
5

说明

对于第 1 组询问 $[1,2]$：$d(1)=1$ 不是素数，$2$ 是素数且 $d(2)=2$ 是素数，因此有 1 个星数。

对于第 2 组询问 $[4,8]$：$4=2^2$，$d(4)=3$ 是素数；$5$ 是素数，$d(5)=2$ 是素数；$6$ 有 $d(6)=4$ 不是素数；$7$ 是素数，$d(7)=2$ 是素数；$8=2^3$，$d(8)=4$ 不是素数。因此共有 3 个星数（$4$，$5$，$7$）。

对于第 3 组询问 $[16,25]$：星数包括 $16=2^4$（$d(16)=5$ 是素数），$17$（素数），$19$（素数），$23$（素数），$25=5^2$（$d(25)=3$ 是素数）。其余数 $18,20,21,22,24$ 的因子个数不是素数。共有 5 个星数。

样例2

输入

2
1 1
6 6

输出

0
0

说明

对于第 1 组询问 $[1,1]$：$d(1)=1$ 不是素数，因此区间内有 0 个星数。

对于第 2 组询问 $[6,6]$：$6=2 \\times 3$，其正因子个数 $d(6)=4$ 不是素数，因此也有 0 个星数。

样例3

输入

3
9 20
100 200
1 100

输出

6
23
32

说明

对于第 1 组询问 $[9,20]$：星数包括 $9=3^2$（$d(9)=3$），$11$、$13$、$17$、$19$ 四个素数，以及 $16=2^4$（$d(16)=5$）。合计 6 个。

对于第 2 组询问 $[100,200]$：星数由两部分组成：指数 $a=1$ 的素数共 21 个（$101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199$）；指数 $a \\ge 2$ 且 $a+1$ 为素数的特殊素数幂有 $121=11^2$ 和 $169=13^2$。合计 $21+2=23$ 个。

对于第 3 组询问 $[1,100]$：素数有 25 个（$2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97$），特殊素数幂有 $2^2=4$，$3^2=9$，$2^4=16$，$5^2=25$，$7^2=49$，$2^6=64$，$3^4=81$，共 7 个。合计 $25+7=32$ 个星数。