CF546D.Soldier and Number Game

Two soldiers are playing a game. At the beginning first of them chooses a positive integer n and gives it to the second soldier. Then the second one tries to make maximum possible number of rounds. Each round consists of choosing a positive integer x > 1, such that n is divisible by x and replacing n with n / x. When n becomes equal to 1 and there is no more possible valid moves the game is over and the score of the second soldier is equal to the number of rounds he performed.

To make the game more interesting, first soldier chooses n of form a! / b! for some positive integer a and b (a ≥ b). Here by k! we denote the factorial of k that is defined as a product of all positive integers not large than k.

What is the maximum possible score of the second soldier?

两名士兵正在玩一个游戏。游戏开始时，第一名士兵选择一个正整数 $n$ 并将其交给第二名士兵。随后，第二名士兵试图进行尽可能多的轮次。每一轮包括选择一个大于 1 的正整数 $x$，使得 $n$ 能被 $x$ 整除，并将 $n$ 替换为 $n/x$。当 $n$ 变为 1 且不再存在合法操作时，游戏结束，第二名士兵的得分即为其执行的轮次数。

为了使游戏更有趣，第一名士兵所选的 $n$ 具有形式 $a! / b!$，其中 $a$ 和 $b$ 为正整数且满足 $a \geq b$。这里 $k!$ 表示 $k$ 的阶乘，定义为所有不超过 $k$ 的正整数的乘积。

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

First line of input consists of single integer t (1 ≤ t ≤ 1 000 000) denoting number of games soldiers play.

Then follow t lines, each contains pair of integers a and b (1 ≤ b ≤ a ≤ 5 000 000) defining the value of n for a game.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 1\,000\,000$），表示士兵们进行的游戏场数。

接下来是 $t$ 行，每行包含一对整数 $a$ 和 $b$（$1 \leq b \leq a \leq 5\,000\,000$），用于定义一场游戏中 $n$ 的值。

For each game output a maximum score that the second soldier can get.

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