2016 ACM ICPC Asia Nha Trang Regional Contest Replay

Start

2017-10-15 12:00 UTC

2016 ACM ICPC Asia Nha Trang Regional Contest Replay

End

2017-10-15 17:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -427 days 13:22:40

Time elapsed

5:00:00

Time remaining

0:00:00

Problem I
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 serveral datasets. The first liine of the input conatins 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, write out on one line the result modulo ${10}^{9}+7$.

Sample Input 1 Sample Output 1
4
2 4
2 5
2 6
2 7
2
4
8
16