G. Multiple Game
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob play a game on two positive integers $$$x$$$ and $$$y$$$. They take turns alternatively, with Alice making the first move. In a move, a player can subtract a multiple of one number from the other number. After the operation, both should remain non-negative. The first person to make the value of $$$x \cdot y$$$ equal to $$$0$$$ wins.

An example of the game on $$$x = 4$$$, $$$y = 14$$$:

  • Alice subtracts $$$8$$$ (a multiple of $$$x=4$$$) from $$$y = 14$$$. Now, $$$x = 4$$$ and $$$y = 6$$$;
  • Bob subtracts $$$4$$$ (a multiple of $$$x=4$$$) from $$$y = 6$$$. Now, $$$x = 4$$$ and $$$y = 2$$$;
  • Alice subtracts $$$4$$$ (a multiple of $$$y=2$$$) from $$$x = 4$$$. Now, $$$x = 0$$$ and $$$y = 2$$$. After that, Alice wins since $$$x \cdot y = 0$$$.

Given two positive integers $$$l$$$ and $$$r\ (l \le r)$$$. Your task is to find the number of ordered pairs $$$(x,y)$$$ such that $$$l \le x \le y \le r$$$ and Alice wins for these pairs.

Input

The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$).

For each test case, the only line contains two space-separated integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 10^9$$$).

Output

For each test case output a single number in a new line  — the number of ordered pairs for which Alice will win.

Example
Input
4
1 3
4 5
66 999
1 1000000
Output
5
2
247645
309017803391
Note

In the first test case, the ordered pairs for which Alice will win are $$$(1,1),(1,2),(1,3),(2,2)$$$ and $$$(3,3)$$$.

In the second test case, the ordered pairs for which Alice will win are $$$(4,4)$$$ and $$$(5,5)$$$.