SOLVE
LATER
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 :
Note: Use Fast I/O to handle large test files.
For the first test case , sequence will be 7,8,9,10. Here, 7,10 are the beautiful numbers, so C=2 .
So, beauty of the sequence = 2^4 = 16 .
For the second test case, sequence is 24,25,26,27,28. Here, 26 is the only beautiful number, so C=1.
Therefore, Beauty of the sequence = 1^5 = 1.