题目描述
Tiwari is very much obsessed with prime numbers. One day he thought to calculate the lowest prime factor of various numbers.
While doing so he came across some numbers called prime number and assumed 0 to be their lowest prime factor (although it's not as we know).
Now ,he gave Anmol (who is Tiwari's competitor) two positive integers L and R and challenged him to calculate the total sum of lowest prime factor of all numbers between L and R (both inclusive).
Now Anmol being a bright student needs your help to finish Tiwari's task. Will you help Anmol?
Since the answer can be very large print your answer modulo (10^9+7).
Input:
First line contains T (no of test cases).
Next T lines contains two positive integers L and R .
Output:
Print T lines of output each containing answer according to the problem statement.
constraints:
1 ≤ T ≤ 10^5
2 ≤ L ≤ R ≤ 10^6
SAMPLE INPUT
2
2 8
3 9
SAMPLE OUTPUT
6
9
Explanation
Test case #1:
numbers in range[2,8] are 2,3,4,5,6,7,8
their lowest prime factors (according to problem statement )are (0,0,2,0,2,0,2) respectively
total sum=0+0+2+0+2+0+2
输入格式
见题面
输出格式
见题面