题目背景

这是一座孤寂的城市……

题目描述

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

定义一个函数 $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$。

数据范围

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