Description

两个士兵正在玩一个游戏，游戏开始的时候，第一个士兵为第二个士兵选一个正整数 $n$。然后第二个士兵要玩尽可能多的轮数。每一轮要选择一个正整数 $x>1$，且n要是x的倍数，然后用 $n/x$ 去代替 $n$。当 $n$ 变成 $1$ 的时候，游戏就结束了，第二个士兵所得的分数就是他玩游戏的轮数。

为了使游戏更加有趣，第一个士兵用 $a! / b!$ 来表示 $n$。$k!$ 表示把所有 $1$ 到 $k$ 的数字乘起来。

那么第二个士兵所能得到的最大分数是多少呢？

Input Format

第一行包含一个整数 $t (1 ≤ t ≤ 1E6)$，表示士兵玩游戏的次数。接下来 $t$ 行，每行包含两个整数 $a,b (1 ≤ b ≤ a ≤ 5E6)$

Output Format

输出一个整数表示答案

2
3 1
6 3

2
5

Source

Online Judge http://127.0.0.1