D. 士兵与数字游戏
每次测试时间限制：$3$ 秒
内存限制：$256$ 兆字节

两名士兵正在玩一个游戏。开始时，第一名士兵选择一个正整数 $n$ 并将其交给第二名士兵。然后第二名士兵尝试进行尽可能多的回合。每回合包括：选择一个大于 $1$ 的正整数 $x$，使得 $n$ 能被 $x$ 整除，然后将 $n$ 替换为 $n / x$。当 $n$ 变为 $1$ 且无法再进行有效操作时，游戏结束，第二名士兵的得分等于他进行的回合数。

为了使游戏更有趣，第一名士兵选择的 $n$ 形如 $a! / b!$，其中 $a$ 和 $b$ 是正整数（$a \ge b$）。这里 $k!$ 表示 $k$ 的阶乘，定义为所有不超过 $k$ 的正整数的乘积。

第二名士兵能获得的最大得分是多少？

输入
第一行包含一个整数 $t$（$1 \le t \le 10^6$），表示游戏的数量。
接下来 $t$ 行，每行包含两个整数 $a$ 和 $b$（$1 \le b \le a \le 5 \times 10^6$），定义了一个游戏的 $n$ 值。

输出
对于每个游戏，输出第二名士兵能获得的最大得分。

示例

输入

2
3 1
6 3

输出

2
5