You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

土拨鼠 小北 和土拨鼠 辰辰 在一起玩游戏, 他们想知道一个整数 $x$ 的最大价值是多少.

题目描述

定义一个数 $x$ 的最大价值为: 将这个数分解成若干个正整数$a_1 * a_2 * ... * a_k$, 一个数$a_i$只能有一个质因子, 且不同的两个数$a_i, a_j$的最大公约数为$1$

即: $i \neq j, gcd(a_i, a_j) = 1$

分解之后, 这些正整数的和 $\sum a_i$ 就是这个数的价值, 特殊定义 $1$ 的价值为 0.

多次询问, 每次给定闭区间 $[l, r]$ , 计算 $[l, r]$ 这个区间内所有数字的价值之和.

数据格式

输入格式

第一行一个整数 $t$ , 表示询问次数

接下来 $t$ 行, 每行两个整数$l, r$, 表示一次询问

输出格式

输出 $t$ 行, 每行一个数值表示答案.

样例

2
2 10
3 20

50
168

5
123 456
12345 67890
54321 98765
11111 66666
1 30000000

34488
370206716
531789835
359508835
46089221049118

数据范围

$1 <= l <= r <= 3*10^7, 1<=t <= 10^4$