Gangwar loves to solve problems and spend all his time either solving problems or playing COC. One day while solving a problem, he defined ‘Beautiful numbers’.

A number ‘N’ is called ‘Beautiful’ if and only if, Count(N) = Sum(N) , where

Count(N) = Count of distinct prime numbers in prime factorization of ‘N’.

Sum(N) = Sum of the powers of prime numbers in prime factorization of ‘N’.

For e.g.:

12 = 2 x 2 x 3 or 2^2 * 3^1 , here count(12) = 2 (2 and 3 are two distinct primes) , and sum(12) = 3 (2+1) , since sum(12) ≠ count(12), so 12 is not a beautiful number.

6 = 2 x 3 or 2^1 * 3^1, here count(6) = 2 (2 and 3 are two distinct primes), and sum(6) = 2 (1+1) , since sum(6)=count(6) , so 6 is a beautiful number.

‘1’ is considered as a Beautiful number.

Let ‘C’ be the count of ‘Beautiful Numbers’ in a range L to R (both inclusive) , then beauty of the sequence , L,L+1,L+2,L+3,……,R-3,R-2,R-1,R is given by ,

                    pow( C, (R-L+1) ) or C ^ (R-L+1)

As, Gangwar is busy trying to find appropriate strategy for his Clan War in COC, he asks you to find the Beauty of the sequence defined by the numbers L and R.

Input:

First line of input contains integer T, i.e. the number of test cases.

Each test case contains 2 space separated integers L and R.

Output :

For each test case, print a single new line containing the beauty of the sequence defined by L and R.

Since, the beauty of the sequence can be very large output it modulo 1000000007 (10^9 + 7).

Constraint :

• 1<=T<=1000000
• 0<=L<=1000000
• 0<=R<=1000000
• L<=R

Note: Use Fast I/O to handle large test files.