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