Gangwar's Beautiful Numbers
Tag(s):

## Easy

Problem
Editorial
Analytics

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.

SAMPLE INPUT
2
7 10
24 28
SAMPLE OUTPUT
16
1
Explanation

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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

CodeMaze v3.0

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Greedy Algorithms
• Algorithms > Searching
• Algorithms > Graphs
• Algorithms > Dynamic Programming
• Data Structures > Advanced Data Structures
• Math > Basic Math