A16664 | Zero Trailing Factorial

对于所有正整数 $x \geq 1$ 和 $k \geq 2$，定义 $v_k(x!)$ 表示在 $x! = x \cdot (x-1) \cdots 1$ 的 $k$ 进制表示下末尾零的个数。形式上，$v_k(x!)$ 被定义为最大的整数 $i$，使得 $k^i$ 整除 $x!$。

对于一个质数 $p$，可以通过公式 $v_p(x!) = \sum\limits_{j=1}^\infty \left\lfloor \frac{x}{p^j}\right\rfloor$ $^{\text{∗}}$ 计算。如果 $k$ 不是质数，将其素因数分解为 $k = \prod p_i^{e_i}$，其中 $p_i$ 是不同的质因子，$e_i$ 是对应的指数。此时，
$$ v_k(x!) = \min\limits_i \left\lfloor \frac{v_{p_i}(x!)}{e_i}\right\rfloor. $$

对于任意两个正整数 $a$ 和 $b$，以及任意整数 $k \ge 2$，定义数对 $(a, b)$ 在 $k$ 下的权重 $w_k(a, b)$，如下：
$$ w_k(a, b) = \begin{cases} \min(v_k(a!), v_k(b!)) & \text{if } v_k(a!) \neq v_k(b!)；\\ 10^{100} & \text{otherwise.} \end{cases} $$

进一步，定义 $f_m(a, b)$ 为 $k$ 取遍 $2 \le k \le m$ 时 $(a, b)$ 的最小权重：
$$ f_m(a, b) = \min\limits_{2 \le k \le m} w_k(a, b). $$

现给定两个整数 $n$ 和 $m$，你的任务是计算 $\sum_{1 \le x \le n - 1} f_m(x, n)$。

可以证明，在给定约束下，结果严格小于 $10^{100}$。

$^{\text{∗}}$ 这里 $\lfloor y \rfloor$ 表示 $y$ 的 [向下取整](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions)，即小于等于 $y$ 的最大整数。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的组数。

每组测试数据的一行包含两个整数 $n$ 和 $m$（$2 \le n \le m \le 10^7$）——分别表示函数的参数。

注意，所有测试数据中 $n$ 和 $m$ 的总和没有额外限制。

对于每组测试数据，输出一行一个整数，表示 $\sum\limits_{1 \le x \le n-1} f_m(x, n)$ 的结果。