题目描述

“Sendai，你是笨蛋吗？”

——宫城咏

只需花费 5000 日元，宫城就能让 Sendai 做任何她想做的事！今天，宫城要求 Sendai 帮她构造一个数组……不过她只想要一种非常特殊的数组。

对于任意整数 $b \geq 2$ 和 $x \geq 1$，定义 $v(b, x)$ 为满足 $b^k \mid x$ 的最大 $k$；也就是说，最大的 $k$ 使得 $x$ 是 $b^k$ 的倍数。可以证明，这个值总是一个定义良好的非负整数。

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

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

输入格式

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

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

保证所有测试用例中 $m$ 的总和不超过 $2 \times 10^5$。

输出格式

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

样例

6
4 20
6 6
6 216
3 500
2 8
5 29

7
5
19
13
3
9

样例说明

在第一个例子中，可以选择数组 $a = [6, 8, 9, 16]$，其计算值为 $3 + 2 + 2 = 7$。

可以证明，这就是所有满足条件的长度为 $n$ 的数组 $a$ 中，使 $\sum_{i=2}^n v(i, a_i)$ 最大的结果。

由 ChatGPT 5 翻译

来源

Codeforces 2171H，英文题名 Shiori Miyagi and Maximum Array Score。