该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

对于任意正整数$n$，$n$的阶乘被定义为$n!=1* 2 * 3* ...* n$,例如$7!=1* 2* 3* 4* 5* 6* 7 = 5040。$

如果对阶乘进行质因数分解，我们能发现每个质数出现的频率，例如$7!=2^4 * 3^2 * 5 * 7$, $2$出现了$4$次，$3$出现了$2$次，$5$出现了$1$次，$7$出现了$1$次。

对区间$[L,R]$的每一个正整数的阶乘进行质因数分解，分别统计出现频率为$1$的质数个数，并累加求和得出总个数$S$。

输入格式

第一行仅包含一个正整数$T$，表示共包含$T$组测试样例。

对于每组测试样例，包含两个正整数$L$和$R$，表示区间的左右端点。

输出格式

对于每组测试样例产生一行输出，包含一个正整数$S$，表示区间内每一个正整数阶乘质因数分解结果中出现频率为$1$的质数的总个数。

2
1 5
7 10

6
7

样例说明

$2! = 2 (1)$

$3! = 2 * 3 (2)$

$4! = 2^3 * 3 (1)$

$5!= 2^3 * 3* 5 (2)$

所以区间$[1, 5]$中 $2！$包含$1$个只出现$1$次的质数2,

$3！$包含$2$个只出现$1$次的质数$2$和$3$,

$4！$包含$1$个只出现$1$次的质数$3$,

$5！$包含$2$个只出现$1$次的质数$3$ 和$5$,

所以区间$[1, 5]$正整数阶乘质因数分解一共包含$1+2+1+2=6$个出现频率为$1$的质数。

$7! = 2^4* 3^2 *5 *7 (2)$

$8! = 2^7* 3^2 * 5 * 7 (2)$

$9! = 2^7* 3^4 * 5 * 7 (2)$

$10!＝2^8* 3^4 * 5^2 * 7 (1)$

所以区间$[7, 10]$中

$7!$包含$2$个只出现1次的质数$5$和$7$，

$8!$包含$2$个只出现1次的质数$5$和$7$,

$9！$包含$2$个只出现1次的质数$5$和$7$,

$10!$包含$1$个只出现1次的质数$7$,

所以区间[7,10]正整数阶乘质因数分解共包含$2+2+2+1= 7$个出现频率为$1$的质数。

数据范围

• 测试点1：$1≤T≤10,1≤L≤R≤10$；

• 测试点2：$1≤T≤10,1≤L≤R≤20$；

• 测试点3：$1≤T≤10,1≤L≤R≤10^6$​ ，特殊要求$L=R$；

• 测试点4，5：$1≤T≤10,1≤L≤R≤100$；

• 测试点6，7，8：$1≤T≤1000,1≤L≤R≤100$；

• 测试点9：$1≤T≤10^5 ,1≤L≤R≤10^5$

• 测试点10：$1≤T≤10^6 ,1≤L≤R≤10^6$