两个士兵正在玩游戏。一开始,他们中的第一个选择一个正整数 n 并将其交给第二个士兵。然后第二个尝试进行最大可能的回合数。每轮包括选择一个正整数 x > 1,使得 n 可被 x 整除,并将 n 替换为 n / x。当 n 等于 1 并且不再有可能的有效移动时,游戏结束,第二个士兵的分数等于他执行的回合数。
为了让游戏更有趣,第一个士兵选择a形式的n! /b!对于某个正整数 a 和 b (a ≥ b)。在这里,k!我们表示 k 的阶乘,它被定义为所有不大于 k 的正整数的乘积。
第二个士兵的最大可能得分是多少?
输入
输入的第一行由单个整数 t (1 ≤ t ≤ 1 000 000) 组成,表示士兵玩的游戏数量。
然后是 t 行,每行包含一对整数 a 和 b (1 ≤ b ≤ a ≤ 5 000 000),定义游戏的 n 值。
输出
每场比赛输出第二个士兵可以获得的最高分数。
示例
输入 #1
2 3 1 6 3
输出 #1
2 5