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

题目背景

这是一座孤寂的城市……

题目描述

甘道夫来到了中州的一座城市，这里有很多的巴士站。

定义一个函数 $g(x)$，如果 $x$ 的因数个数为奇质数，$g(x)=1$，否则 $g(x)=0$。

在这座城市里，从巴士站 $l$ 坐到 $r$ 需要 $\sum\limits_{i=l}^r g(i)$ 的代价。

甘道夫想坐 $t$ 次巴士，你能告诉他每一次的代价吗？

输入格式

第一行一个正整数 $t$，表示甘道夫想坐 $t$ 次巴士。

接下来 $t$ 行，每行两个正整数 $l,r$，表示甘道夫从巴士站 $l$ 坐到 $r$。

输出格式

一共 $t$ 行，表示每一次的代价。

样例 #1

样例输入 #1

4

1 4

5 10

4 25

3 9

样例输出 #1

1

1

4

2

提示

样例 $1$ 解释：

$4\sim25$ 中，当 $x=4,9,16,25$ 时 $g(x)=1$。

故询问 $3$ 输出 $4$。

数据范围

子任务	测试点	$t\le$	$l\le r\le$	分值
$1$	$1\sim 3$	$10$	$10^5$	$10$
$2$	$4\sim 6$	$100$	$10^7$
$3$	$7\sim 9$	$10^4$
$4$	$10\sim 14$	$100$	$10^9$	$30$
$5$	$15\sim 19$	$10^4$	$10^{14},l=1$	$10$
$6$	$20\sim 25$		$10^{14}$	$30$

对于 $100\%$ 的数据：$1\le t\le 10^4$，$1\le l\le r\le 10^{14}$。