两个士兵在玩游戏。在开始时，他们中的第一个选择一个正整数n，并将其交给第二个士兵。然后，第二个士兵开始完成尽可能多的回合。每一轮选择一个大于1的正整数x，使得n可被x整除，然后用n/x替换n，当n变为1时游戏结束。第二名士兵的得分等于他执行的轮数。

为了让游戏更有趣，第一名士兵选择用a!/b！来表示n，a和b为正整数（a>=b）。这里k！表示k的阶乘，它被定义为所有不大于k的正整数的乘积。

第二名士兵的最高得分是多少？

第一行输入单个整数t（1<t<1000000），表示士兵玩这个游戏的次数。

接着下面t行，每一行都包含一对整数a和b（1<=b<=a<=5000000），它们定义了一个游戏的n值。

对于每一场比赛，输出第二名士兵可以获得的最高分。