You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

$\texttt{Alice}$ 和 $\texttt{Bob}$ 正在玩一个游戏，游戏初始给定一个正整数 $m$。

两人轮流操作，$\texttt{Alice}$ 先手（第一轮作为操作方进行游戏），每一轮游戏规则如下：

• 操作方指定 $m$ 的一个大于 $1$ 的约数 $x$ ；
• 非操作方需要选择 $m$ 的一个大于 $1$ 的约数 $y$，且 $y \mid x^y$ ；
• $m \leftarrow \frac{m}{y}$ (表示将 $m$ 赋值为 $\frac{m}{y}$)。

若一轮游戏完毕后 $m=1$，则该轮的操作方获胜。

特别的，若初始 $m=1$, 则先手判负。

双方都会按照最优策略进行博弈。设函数 $\mathrm{Game}(n)=1$ 当且仅当游戏的初值为 $n$ 时 $\texttt{Alice}$ 必胜，否则 $\mathrm{Game}(n) = 0$ 。

$q$ 次询问，每次询问给定 $l, r$ ，求 $\sum\limits_{i=l}^{r}\mathrm{Game}(i)$ 的值。

输入格式

第一行，输入一个整数 $q\,(1\le q\le 100)$ ；

接下来 $q$ 行，每行输入两个整数，表示 $l, r\,(1\le l \le r \le 10^9)$ 。

输出格式

对每次询问，输出一行一个整数，表示答案。

输入输出样例 #1

输入 #1

3
4 5
2 9
16 18

输出 #1

1
4
2

说明/提示

考虑第 $1$ 次询问。如果初始的数值为 $4$，那么 $\texttt{Alice}$ 作为操作方要么选择 $2$，要么选择 $4$。不管选择哪个，$\texttt{Bob}$ 都可以选择 $2$，因为 $2\mid 2^2, 2\mid 4^2$ 。然后数值变为 $2$，$\texttt{Bob}$ 只能选择 $2$，$\texttt{Alice}$ 也只能选择 $2$ 。于是数值变为 $1$，$\texttt{Bob}$ 获胜。

如果初始的数值为 $5$，那么 $\texttt{Alice}$ 作为操作方只能选择 $5$，$\texttt{Bob}$ 也只能选择 $5$，数值变为 $1$，$\texttt{Alice}$ 赢下游戏。所以输出 $1$ 。