题目背景

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

题目描述

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

即: $i != 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$