primesum

For a given number N
F ( N ) = N if N is prime
F ( N ) = 0 otherwise 
Given L and R , for all pairs i , j in the range [ L , R ] find the sum of F ( i ) * F ( j ) where j > i modulo 10^9 +7.  

*Input : *
First line contains T ≤ 1000000. Number of TestCases

Next T lines contain 2 integers L , R

1 ≤ L ≤ R ≤ 10^6

Output :

For each test case, output a single integer denoting the answer of the problem modulo 10^9 +7.

SAMPLE INPUT
1
1 10

SAMPLE OUTPUT
101

Explanation

Prime numbers between 1 and 10 are 2,3,5,7.

So the ans is (2 * 3 + 2 * 5 + 2 * 7 + 3 * 5 + 3 * 7 + 5 * 7 ) modulo 10^9+7 = 101

Source: hackerearth | Difficulty: EASY
Tags: Number theory


Solutions: