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

Read the editorial here.