Problem J
Divisor Game

RR and Flash are playing a game with a list of numbers that are distinct initially. In this game two players will take alternative turns. In each turn, a player can select a number $X$ in the list and replace it with number $D$ iff $D$ is a divisor of $X$ and $D$ is smaller than $X$.

For example, with the list $(1, 3, 12)$, the valid moves are:

• replacing $12$ with one of the following number: $1, 2, 3, 4$ or $6$;

• replacing $3$ with $1$.

The player who takes the last move will lose the game. At the beginning, Flash will select a non-empty initial list of distinct numbers between $A$ and $B$ inclusively and RR is the one who makes the first move.

Your task is to calculate the number of possible ways for Flash to select the initial list where he can be sure that he would win the game assuming both players play optimally.

Input

The input consists of several datasets. The first line of the input contains the number of datasets which is a positive number and is not greater than $100$. The following lines describe the datasets. Each dataset is described in a single line containing two integers $A$ and $B$ $(1 < A \leq B \leq {10}^{12}, B - A \leq {10}^{5})$.

Output

For each dataset, output the result modulo ${10}^{9}+7$.

4
2 4
2 5
2 6
2 7

2
4
8
16