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$$$.

Input

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.

Output

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

Note

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$$$.

Zero Trailing Factorial

Examples