对于所有正整数 $$$x\ge 1$$$ 和 $$$k\ge 2$$$,让 $$$v_k(x!)$$$ 表示 $$$x! 的基 $$$k$$$ 表示中尾随零的数量! = x\cdot (x-1)\cdot \ldots \cdot 1$$$。形式上,$$$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!)\text{;}\\10^{100} & \text{否则。}\end{cases}$$
接下来,将 $$$f_m(a, b)$$$ 定义为 $$$(a, b)$$$ 相对于 $$$k$$$ 的最小权重,用 $$$2\le k\le m$$$ 接管所有整数 $$$k$$$: $$f_m(a, b)=\min\limits_{2\le k\le m}w_k(a, b).$$
给你两个整数 $$$n$$$ 和 $$$m$$$。您的任务是计算所有小于 $$$n$$$ 的正整数 $$$f_m(x, n)$$$ 的总和: $$\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)$$$ 的整数。
示例
输入复制
53 56 76 1036 6810000000 10000000
输出复制
01013279933
注意
在第一个测试用例中,考虑 $$$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$$$,因为 $$$6^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$$$。