← 返回题目列表

Codeforces · 546/D

D. 士兵与数字游戏

中文机器翻译题面 查看原题

两个士兵正在玩游戏。一开始,他们中的第一个选择一个正整数 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