F-「SFCOI-4」追忆的残响

时间限制：C/C++/Rust/Pascal 10秒，其他语言20秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 想起来想起来还有天高山水长
$\hspace{15pt}$ 你是翅膀也是我肩膀
$\hspace{15pt}$ 祝每一位我的朋友，都能记起算法带给你的最初的感动或者快乐。

$\hspace{15pt}$ 符号约定：对于正整数 $n \geq 2$ ，记 $\operatorname{mpf}(n)$ 表示 $n$ 的最大质因数；对于一棵有根树 $T$ 和 $x, y \in T$ ，记 $\operatorname{lca}(x, y)$ 表示 $x, y$ 在 $T$ 上的最近公共祖先编号。

$\hspace{15pt}$ 给定一棵以 $1$ 为根的有标号有根树，满足：
$\hspace{23pt}\bullet\,$ 节点编号为正整数；
$\hspace{23pt}\bullet\,$ 对于正整数 $i \geq 2$ ， $i$ 的父亲为 $\tfrac{i}{\operatorname{mpf}(i)}$ 。

$\hspace{15pt}$ 现在，给定 $n, m$ ，请你求出 $\displaystyle\sum_{i = 1}^n \sum_{j = 1}^m \operatorname{lca}(i, j)$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

在一行上输入两个整数 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示所求式子的答案。

示例1

输入

复制

8
1 10
10 100
100 1000
1000 10000
10000 100000
100000 1000000
1000000 10000000
10000000 15000000

输出

复制

10
1610
180246
18624306
1895429750
191959886222
19387609896042
335608998269392