CF2153E.Zero Trailing Factorial

For all positive integers $x\ge 1$ and $k\ge 2$, let $v_k(x!)$ denote the number of trailing zeros in the base-$k$ representation of $x! = x\cdot (x-1)\cdot \ldots \cdot 1$. Formally, $v_k(x!)$ is defined as the largest integer $i$ such that $k^i$ divides $x!$.

For a prime number $p$, we can calculate $v_p(x!) = \sum\limits_{j=1}^\infty \left\lfloor \frac{x}{p^j}\right\rfloor$$^{\text{∗}}$. If $k$ is not prime, write its prime factorization as $k = \prod p_i^{e_i}$, where $p_i$ are distinct prime factors and $e_i$ are their corresponding exponents. Then, $$v_k(x!) = \min\limits_i \left\lfloor \frac{v_{p_i}(x!)}{e_i}\right\rfloor.$$

For any two positive integers $a$ and $b$, and any integer $k\ge 2$, the weight of the pair $(a, b)$ with respect to $k$, denoted by $w_k(a, b)$, is defined as $$w_k(a, b) = \begin{cases}\min(v_k(a!), v_k(b!)) & \text{if }v_k(a!)\neq v_k(b!)\text{;}\\10^{100} & \text{otherwise.}\end{cases}$$

Next, define $f_m(a, b)$ as the minimum weight of the pair $(a, b)$ with respect to $k$, taken over all integers $k$ with $2\le k\le m$: $$f_m(a, b)=\min\limits_{2\le k\le m}w_k(a, b).$$

You are given two integers $n$ and $m$. Your task is to compute the sum of $f_m(x, n)$ over all positive integers $x$ less than $n$: $$\sum_{1\le x\le n - 1} f_m(x, n).$$

It can be shown that under the given constraints, the result is strictly less than $10^{100}$.

$^{\text{∗}}$$\lfloor y\rfloor$ denotes the floor of $y$, which is the greatest integer less than or equal to $y$.

对于所有正整数 $x\ge 1$ 和 $k\ge 2$，记 $v_k(x!)$ 为 $x! = x\cdot (x-1)\cdot \ldots \cdot 1$ 在 $k$ 进制表示下的末尾零的个数。形式上，$v_k(x!)$ 定义为满足 $k^i \mid x!$ 的最大整数 $i$。

对于素数 $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{若 }v\_k(a!)\\neq v\_k(b!)\\text{;}\\\\10^{100} & \\text{否则。}\\end{cases}

接着，定义 $f_m(a, b)$ 为在所有满足 $2\le k\le m$ 的整数 $k$ 中，数对 $(a, b)$ 关于 $k$ 的权值的最小值：

$$f\_m(a, b)=\\min\\limits\_{2\\le k\\le m}w\_k(a, b).$$

给定两个整数 $n$ 和 $m$，你的任务是计算所有小于 $n$ 的正整数 $x$ 对应的 $f_m(x, n)$ 之和：

$$\\sum\_{1\\le x\\le n - 1} f\_m(x, n).$$

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

$^{\text{∗}}$$\lfloor y\rfloor$ 表示 $y$ 的向下取整，即不超过 $y$ 的最大整数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first and only line of each test case contains two integers $n$ and $m$ ($2\le n\le m\le 10^7$) — the parameters of the function.

Note that there are no constraints on the sum of $n, m$ over all test cases.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

每个测试用例仅有一行，包含两个整数 $n$ 和 $m$（$2\le n\le m\le 10^7$）——该函数的参数。

注意：所有测试用例的 $n$ 与 $m$ 的总和没有额外限制。

For each test case, output a single integer representing $\sum\limits_{1\le x\le n - 1} f_m(x, n)$.

对于每个测试用例，输出一个整数，表示 $\sum\limits_{1\le x\le n - 1} f_m(x, n)$。

In the first test case, consider $k = 3\le 5$:

• $v_3(1!) = v_3(2!) = 0$, since $3$ does not divide both $1$ and $2$.
• $v_3(3!) = v_3(6) = 1$, since $3$ divides $6$, but $3^2 = 9$ does not.

Therefore, $w_3(1, 3) = w_3(2, 3) = \min(0, 1) = 0$. It can be shown that this is the minimum weight across all $2\le k\le 5$, so $f_5(1, 3) = f_5(2, 3) = 0$.

In the second test case, it can be shown that $f_7(1, 6) = f_7(2, 6) = f_7(3, 6) = f_7(4, 6) = 0$. For $f_7(5, 6)$, we consider $k = 6\le 7$:

• $v_6(5!) = v_6(120) = 1$, since $6$ divides $120$, but $6^2 = 36$ does not.
• $v_6(6!) = v_6(720) = 2$, since $6^2 = 36$ divides $720$, but $6^3 = 216$ does not.

Therefore, $w_6(5, 6) = \min(1, 2) = 1$. It can be shown that this is the minimum weight across all $2\le k\le 7$, so $f_7(5, 6) = 1$.

Note: choosing $k = 7 \le 7$ does not work, because $v_7(5!) = v_7(6!) = 0$, so $w_7(5, 6) = 10^{100}$.

In the third test case, it can be shown that $f_{10}(1, 6) = f_{10}(2, 6) = f_{10}(3, 6) = f_{10}(4, 6) = 0$. For $f_{10}(5, 6)$, we consider $k = 9\le 10$:

• $v_9(5!) = v_9(120) = 0$, since $9$ does not divide $120$.
• $v_9(6!) = v_9(720) = 1$, since $9$ divides $720$, but $9^2 = 81$ does not.

Therefore, $w_9(5, 6) = \min(0, 1) = 0$. It can be shown that this is the minimum weight across all $2\le k\le 10$, so $f_{10}(5, 6) = 0$.

在第一个测试用例中，考虑 $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$ 不能整除 $6$。

因此，$w_3(1, 3) = w_3(2, 3) = \min(0, 1) = 0$。可以证明，这是所有满足 $2\le k\le 5$ 的 $k$ 中的最小权值，故 $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$ 不能整除 $120$。
• $v_6(6!) = v_6(720) = 2$，因为 $6^2 = 36$ 能整除 $720$，但 $6^3 = 216$ 不能整除 $720$。

因此，$w_6(5, 6) = \min(1, 2) = 1$。可以证明，这是所有满足 $2\le k\le 7$ 的 $k$ 中的最小权值，故 $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$ 不能整除 $720$。

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