Number Game
Tag(s):

## Algorithms, Hard

Problem
Editorial
Analytics

Alice and Bob are playing a game. They choose some subset of integers from A to B (including A and B). Let us call this subset T. The players alternate turns, with Alice being the first to play. In each turn player will choose a number from T and replace it with one of its factor such that the number being replaced is less than the original number. Note that T can have multiple identical elements at some point in the game. If a player cannot make a move, he will lose.

For given numbers A and B, Alice wants to know the number of subsets T such that he will win the game always. If both the players play optimally, count the number of such subsets.

Input
First line of the input contains the number of test cases T. It is followed by T lines. Each line contains two space separated integers A and B.

Output
For each test case print a single number, the number of sucn subsets. As the answer can be large, print the answer modulo 1000000007.

Constraints
1 <= T <= 10
1 <= A <= B <= 10^10
B - A <= 10^5

SAMPLE INPUT
4
1 5
3 10
2 4
5 15

SAMPLE OUTPUT
24
192
6
1536

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 1020 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

September Rush

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Basic Programming > Implementation
• Algorithms > Dynamic Programming
• Algorithms > Sorting