题目背景

这是一座孤寂的城市……

题目描述

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

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

| $3$ | $7\sim 9$ | $10^4$ | $10^7$ | $10$ |

| $4$ | $10\sim 14$ | $100$ | $10^9$ | $30$ |

| $5$ | $15\sim 19$ | $10^4$ | $10^{14},l=1$ | $10$ |

| $5$ | $20\sim 25$ | $10^4$ | $10^{14}$ | $30$ |

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