CFCF2153E.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$ 的 向下取整，即小于等于 $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)$ 的结果。

在第一个测试点中，考虑 $k=3 \le 5$：

• $v_3(1!)=v_3(2!)=0$，因为 $3$ 不能整除 $1!$ 与 $2!$。
• $v_3(3!) = v_3(6) = 1$，因为 $3$ 能整除 $6$，但 $3^2 = 9$ 不能。

因此，$w_3(1, 3)=w_3(2, 3)=\min(0,1)=0$。可以证明这是所有 $2 \le k \le 5$ 中的最小权重，所以 $f_5(1, 3)=f_5(2, 3)=0$。

在第二个测试点中，可以证明 $f_7(1, 6)=f_7(2, 6)=f_7(3, 6)=f_7(4, 6)=0$。对于 $f_7(5, 6)$，考虑 $k=6 \le 7$：

• $v_6(5!) = v_6(120) = 1$，因为 $6$ 能整除 $120$，但 $6^2 = 36$ 不能。
• $v_6(6!) = v_6(720) = 2$，因为 $36$ 能整除 $720$，但 $6^3 = 216$ 不能。

因此 $w_6(5, 6) = \min(1, 2) = 1$。可以证明这是所有 $2 \le k \le 7$ 中的最小权重，所以 $f_7(5, 6) = 1$。

注意：选择 $k = 7 \le 7$ 无法取得更优，因为 $v_7(5!) = v_7(6!) = 0$，这时 $w_7(5, 6) = 10^{100}$。

在第三个测试点中，可以证明 $f_{10}(1, 6) = f_{10}(2, 6) = f_{10}(3, 6) = f_{10}(4, 6) = 0$。对于 $f_{10}(5, 6)$，考虑 $k=9 \le 10$：

• $v_9(5!) = v_9(120) = 0$，因为 $9$ 不能整除 $120$。
• $v_9(6!) = v_9(720) = 1$，因为 $9$ 能整除 $720$，但 $9^2 = 81$ 不能。

因此 $w_9(5, 6) = \min(0, 1) = 0$。可以证明这是所有 $2 \le k \le 10$ 的最小权重，所以 $f_{10}(5, 6) = 0$。