「你是傻子吗,仙台同学?」
— 宫城诗织
只要花5000日元的费用,宫城就可以让仙台为所欲为!今天,宫城要求仙台为她制作阵法……具体来说,宫城只想要一种非常特殊的阵法。
对于任意整数 $$$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 \lt 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\cdot 10^5$$$)。
保证所有测试用例的 $$$m$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数,即满足给定条件的长度为 $$$n$$$ 的所有数组 $$$a$$$ 中 $$$\sum_{i=2}^n v(i, a_i)$$$ 的最大值。
示例
输入复制
64 206 66 2163 5002 85 29
输出复制
75191339
注意
在第一个示例中,一个可能的数组是 $$$a = [6, 8, 9, 16]$$$,它产生的值是 $$$3 + 2 + 2 = 7$$$。
可以证明,这是满足给定条件的长度为 $$$n$$$ 的所有数组 $$$a$$$ 中 $$$\sum_{i=2}^n v(i, a_i)$$$ 的最大值。