Nafis Shahriar loves to do codeforces programming contests. He is the first candidate master in codeforces from MBSTU. One day he found a problem. As he was busy practicing the suffix array, he gave the problem to his juniors.
The problem is:
Let’s define a function F(x)= sum of all divisors of x where a divisor is a square number.
You will get two integers L, R.
You have to calculate the sum of $ \sum_{i=L+1}^R F(i) $
The first line of the input contains a single integer T( 1<= T <=10 ) denoting the number of test cases.
The description of T test cases follows.
Each case contains two integers L, R( 0<=L<=R<= 1018 ).
For each test case, print a single line containing one integer ― the sum modulo 1,000,000,007 (109+7).
Input | Output |
---|---|
2 1 20 5 9 | 73 17 |
F(1)=1 , F(2)=1 , F(3)=1 , F(4)=1+4=5 , F(5)=1
F(6)=1 , F(7)=1 , F(8)=1+4=5 , F(9)=1+9=10
For F(9) , 9 has 3 divisors 1,3,9 . 1 and 9 is square number . sum is 1+9=10
For The second case , F(6)+F(7)+F(8)+F(9) = 1+1+5+10 = 17