题目描述

对于任意正整数n，n的阶乘被定义为 n!=1×2×3×4×……×n，例如7!=1×2×3×4×5×6×7=5040。如果对阶乘进行质因数分解，我们能发现每个质数出现的频率，例如7! = 2⁴ × 3² × 5 × 7，2出现了4次，3出现了2次，5出现了1次，7出现了1次。对区间[L，R]的每一个正整数的阶乘进行质因数分解，分别统计出现频率为1的质数的个数，并累加求和得出总个数S。

输入描述

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

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

输出描述

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

样例1

输入

2

1 5

7 10

输出

6

7

提示

测试点1：1≤T≤10,1≤L≤R≤10;

测试点2：1≤T≤10,1≤L≤R≤20;

测试点3：1≤T≤10,1≤L≤R≤10⁶特殊要求: 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⁵,1≤L≤R≤10⁵;

测试点10：1≤T≤10⁶,1≤L≤R≤10⁶.

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

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

测试点1：1≤T≤10,1≤L≤R≤10;

测试点2：1≤T≤10,1≤L≤R≤20;

测试点3：1≤T≤10,1≤L≤R≤10⁶特殊要求: 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⁵,1≤L≤R≤10⁵;

测试点10：1≤T≤10⁶,1≤L≤R≤10⁶.