暂无测试数据。

题目背景

小G 和小 Y 想要玩游戏。

老师说：在玩游戏之前需要先解决一个问题，将问题解决后才能去玩游戏。

题目描述

定义一个数的 $x$ 价值为：将这个数分解成若干个正整数 $a_1,a_2,\cdots,a_k$ （k 是任意可行正整数）的乘积的形式($x = a_1 \times a_2 \times \cdots \times a_k$)。一个数 $a_i$ 只能有一个质因子，且不同的两个数 $a_i,a_j$，满足：$i\neq j,\gcd(a_i,a_j)=1$，即两个数之间不能有公共的质因子。

分解之后，这些正整数的和（$\sum a_i$）就是这个数的价值。特殊定义：$1$ 的价值为 $0$。

多组询问，每次询问给定 $L,R$，求大小在 $L\sim R$ 范围内的所有数的价值之和。

注意题目出现的数全是正整数。

输入格式

第一行一个整数 $T$，表示询问次数。

接下来的 $T$ 行，两个整数 $L,R$，含义如上文所示。

输出格式

共 $T$ 行，要求对每个询问，输出一个数表示答案。

数据范围

对于 $30\%$ 的数据：$1\le L,R\le 100,\sum(R-L)\le 1000$；

另有 $10\%$​ 的数据：$T=1$​；

对于 $60\%$ 的数据：$1\le L\le R\le 10^6,1\le T\le 10^4$。

对于 $100\%$ 的数据：$1\le L\le R\le 3\times 10^7,1\le T\le 10^4$。

1
2 10

50

5
16358 780648
5092 757841
25143 780537
10652 761059
25963 758607

40512137858
38287070746
40469137885
38597181844
38301280803