#P18439. A Simple MST Problem

A Simple MST Problem

A Simple MST Problem

  • 标准输入、标准输出。

题目描述

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

在本题中,把每个正整数看作一个结点。在结点 xx 和结点 yy 之间连一条边的花费为 ω(lcm⁡(x,y))\omega(\operatorname{lcm}(x,y)),其中 lcm⁡\operatorname{lcm} 表示最小公倍数。

现在有 TT 个询问。第 ii 个询问给出两个整数 li,ril_i,r_i。仅考虑结点 li,li+1,…,ril_i,l_i+1,\ldots,r_i,求修建若干条边,使这些结点两两可达的最小总花费。

所有询问互不相同。对于一次询问,只允许在 li≤x,y≤ril_i\le x,y\le r_i 的结点之间连边。

输入格式

第一行包含一个整数 TT(T≤50000T\le50000),表示询问数。

接下来 TT 行,每行两个整数 li,ril_i,r_i(1≤li≤ri≤1061\le l_i\le r_i\le10^6),表示一个询问。

保证所有询问互不相同,并且

∑i=1Tri≤106.\sum_{i=1}^{T}r_i\le10^6.

注意这个总限制是 右端点之和,并非区间长度之和。

输出格式

对于每个询问,输出一行一个整数,表示答案。

原样例 1

输入:

5
1 1
4 5
1 4
1 9
19 810

输出:

0
2
3
9
1812

原样例 2

输入:

2
27 30
183704 252609

输出:

8
223092