#P7985. Pty loves lcm

Pty loves lcm

Pty loves lcm

题目描述

Let lcm⁡\operatorname{lcm} denote the least common multiple and let Euler's totient be

φ(z)=∑u=1z[gcd⁡(z,u)=1].\varphi(z)=\sum_{u=1}^{z}[\gcd(z,u)=1].

For positive integers x<yx<y, define

f(x,y)=lcm⁡(x,x+1,…,y).f(x,y)=\operatorname{lcm}(x,x+1,\ldots,y).

Given L,RL,R, compute

$$\sum_{x=1}^{\infty}\sum_{y=x+1}^{\infty}\varphi(f(x,y))[L\le f(x,y)\le R]\pmod {2^{32}}.$$

The brackets are the indicator of the enclosed condition. Each interval [x,y][x,y] has at least two integers. Different intervals are counted separately even when their least common multiples coincide.

输入格式

The first line contains TT (1≤T≤501\le T\le50). Each case contains L,RL,R (1≤L≤R≤10181\le L\le R\le10^{18}).

输出格式

For each case print the answer modulo 2322^{32} as a nonnegative integer on one line.

样例输入1

5
1 10
1 20
20 60
60 100
123456 1234567

样例输出1

5
25
164
160
158548536