CF2171H.Shiori Miyagi and Maximum Array Score

"Are you stupid, Sendai-san?"

— Shiori Miyagi

For the cost of 5000 yen, Miyagi can ask Sendai to do whatever she wants! Today, Miyagi demands that Sendai make her an array... specifically, Miyagi only wants a very particular type of array.

For arbitrary integers $b\geq 2$ and $x\geq 1$, define $v(b, x)$ to be the maximal $k$ satisfying $b^k \mid x$; that is, the maximal $k$ such that $x$ is a multiple of $b^k$. It can be shown that this is always a well-defined, nonnegative integer.

You are given integers $n$ and $m$ satisfying $n\leq m$. Find the maximum value of $\sum_{i=2}^n v(i, a_i)$ across all arrays $a$ of length $n$ satisfying the following conditions:

• $a$ is strictly increasing; that is, for all $1\leq i\leq n-1$, $a_i \lt a_{i+1}$, and
• for all $1\leq i\leq n$, $1\leq a_i\leq m$.

“你是不是傻，千田君？”

—— 宫城汐里

只需花费 5000 日元，宫城就能要求千田做任何她想让他做的事！今天，宫城要求千田为她构造一个数组……更准确地说，宫城只想要一种非常特殊的数组。

对任意整数 $b\geq 2$ 和 $x\geq 1$，定义 $v(b, x)$ 为满足 $b^k \mid x$ 的最大整数 $k$；即，使得 $x$ 是 $b^k$ 的倍数的最大 $k$。可以证明，该值恒为定义良好且非负的整数。

给定满足 $n\leq m$ 的整数 $n$ 和 $m$。在所有满足以下条件的长度为 $n$ 的数组 $a$ 中，求 $\sum_{i=2}^n v(i, a_i)$ 的最大可能值：

• $a$ 是严格递增的；即，对所有 $1\leq i\leq n-1$，有 $a_i \lt a_{i+1}$；
• 对所有 $1\leq i\leq n$，有 $1\leq a_i\leq m$。

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The only line of each test case contains two integers $n$ and $m$ ($2\leq n\leq m \leq 2\cdot 10^5$).

It is guaranteed that the sum of $m$ over all test cases does not exceed $2\cdot 10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 测试用例的数量。

每个测试用例仅有一行，包含两个整数 $n$ 和 $m$（$2\leq n\leq m \leq 2\cdot 10^5$）。

保证所有测试用例的 $m$ 值之和不超过 $2\cdot 10^5$。

For each test case, output a single integer, the maximum value of $\sum_{i=2}^n v(i, a_i)$ across all arrays $a$ of length $n$ satisfying the given conditions.

对于每个测试用例，输出一个整数，即在所有满足给定条件的长度为 $n$ 的数组 $a$ 中，$\sum_{i=2}^n v(i, a_i)$ 的最大值。

In the first example, one possible array is $a = [6, 8, 9, 16]$ which yields a value of $3 + 2 + 2 = 7$.

It can be shown that this is the maximum value of $\sum_{i=2}^n v(i, a_i)$ across all arrays $a$ of length $n$ satisfying the given conditions.

在第一个例子中，一个可能的数组是 $a = [6, 8, 9, 16]$，其对应的值为 $3 + 2 + 2 = 7$。

可以证明，对于所有满足给定条件的长度为 $n$ 的数组 $a$，该值 $\sum_{i=2}^n v(i, a_i)$ 达到最大值。