Problem Description

lcm($x_1,x_2,...,x_k$) is the least common multiple of {$x_1,x_2,...,x_k$}.

$\phi (x)= {\sum_{y=1}^x} [gcd(x,y)=1]$

Define function f(x,y) = lcm(x,x + 1,...,y-1,y)(x < y)(both x,y are non-negative integers)

Now Pty wants to know $\sum_{x=1}^{+\infty }$$\sum_{y=x+1}^{+\infty}$$\phi (f(x,y)) \times [L ≤ f(x,y) ≤ R]$ modulo $2^{32}$.

Input

The first line contains a single integer T(1 ≤ T ≤ 50)— the number of test cases.

The only line of each test case contains two integers L,R(1 ≤ L ≤ R ≤ $10^{18}$).

Output

For each test case, output the answer modulo $2^{32}$.

5
1 10
1 20
20 60
60 100
123456 1234567

5
25
164
160
158548536