2016 ACM ICPC Asia Nha Trang Regional Contest Replay


2017-10-15 04:00 AKDT

2016 ACM ICPC Asia Nha Trang Regional Contest Replay


2017-10-15 09:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1683 days 5:21:59

Time elapsed


Time remaining


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.


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})$.


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

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