题目描述

对于正整数 $x$，定义 $\omega(x)$ 为其不同的质因子个数。例如 $\omega(1)=0,\omega(8)=1,\omega(12)=2$。

给定正整数 $l\leq r$，可以建立一张有 $r-l+1$ 个点的图，点编号依次为 $l,l+1,\cdots,r$。对于任意两个图中的点 $x,y$，其间都有一条权值为 $\omega(\operatorname{lcm}(x,y))$ 的边，其中 $\operatorname{lcm}(x,y)$ 是 $x,y$ 的最小公倍数。你需要求出这张图的最小生成树的权值和。

注意，在最小生成树中你只能使用图中存在的点（即 $l,l+1,\cdots,r$）之间的边，而不能引入其它节点。

你需要解决 $T$ 组独立的询问。

输入格式

第一行一个整数 $T$ 表示数据组数。

对于每组数据，一行两个整数 $l,r$。

输出格式

对于每组数据，输出一行一个整数表示答案。

7
1 1
4 5
1 4
1 9
19 810
27 30
183704 252609

0
2
3
9
1812
8
223092

数据范围

对于 $30\%$ 的数据，$\sum_{i=1}^{T}r_i\leq 100$。

对于 $60\%$ 的数据，$\sum_{i=1}^T{r_i}\leq 5000$。

对于 $100\%$ 的数据，$1\leq T\leq 5\times 10^4$，$1\leq l_i\leq r_i\leq 10^6$，$\sum_{i=1}^T r_i\leq 10^6$。