题目描述

“两质整数”指能表示成两个质数乘积的整数。 质数——又称为素数，一个大于$1$的自然数，除了$1$和 本身外没有其它因子。 比如：$15$就是“两质整数”，因为$15$可表示成$3$和$5$两个质数的乘积。 本题有$Q$组询问，每次询问$[L, R]$$(0 ＜ L ≤ R)$之间共有多少个“两质整数”。

输入格式

第 1 行包含 1 个正整数$Q$，表示数据组数。

接下来 $Q$ 行， 每行有两个用空格隔开的整数$L_i, R_i(L_i ≤ R_i)$，表示询问区间$[L_i, R_i]$中一共有多少个“两质整数”。

输出格式

$Q$ 行，每行包含一个整数，表示询问的答案。

样例1

2
2 4
3 9

1
3

样例解释

区间 $2 ~ 4$ 中：$4=2*2$，只包含1个两质整数； 区间 $3 ~ 9$ 中：$4=2*2，6=2*3，9=3*3$，包含$3$个两质整数；

样例2

3
10 30
15 50
60 100

7
12
13

数据范围

$1 ≤ Q ≤ 10⁵;$ $1 ≤ Li，Ri ≤ 10⁶。$