#P18439. A Simple MST Problem
A Simple MST Problem
A Simple MST Problem
- 标准输入、标准输出。
题目描述
对于一个正整数 ,定义 为它的不同质因子的个数。例如,,,。
在本题中,把每个正整数看作一个结点。在结点 和结点 之间连一条边的花费为 ,其中 表示最小公倍数。
现在有 个询问。第 个询问给出两个整数 。仅考虑结点 ,求修建若干条边,使这些结点两两可达的最小总花费。
所有询问互不相同。对于一次询问,只允许在 的结点之间连边。
输入格式
第一行包含一个整数 (),表示询问数。
接下来 行,每行两个整数 (),表示一个询问。
保证所有询问互不相同,并且
注意这个总限制是 右端点之和,并非区间长度之和。
输出格式
对于每个询问,输出一行一个整数,表示答案。
原样例 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