Limits 2s, 256 MB

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) $

Input

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 ).

Output

For each test case, print a single line containing one integer ― the sum modulo 1,000,000,007 (109+7).

Sample

InputOutput
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

Submit

Login to submit.

Statistics

33% Solution Ratio
EgorKulikovEarliest, Jul '20
Yasir_ArafatFastest, 0.5s
EgorKulikovLightest, 131 kB
steinumShortest, 753B
Toph uses cookies. By continuing you agree to our Cookie Policy.