Ibti 正在考虑为这个问题起一个适合圆形主题(numerus ternarium)的好标题。他立即想到了三阶导数,但这相当蹩脚,所以他决定加入世界上最好的乐队——Three Days Grace。
给定一个多重集 $$$A$$$,初始大小为 $$$n$$$,其元素是 $$$1$$$ 和 $$$m$$$ 之间的整数。在一项操作中,执行以下操作:
- 从多重集合 $$$A$$$ 中选择一个值 $$$x$$$,然后
- 选择两个整数 $$$p$$$ 和 $$$q$$$ 使得 $$$p, q > 1$$$ 和 $$$p \cdot q = x$$$。将$$$p$$$ 和$$$q$$$ 插入$$$A$$$,从$$$A$$$ 删除$$$x$$$。
请注意,多重集 $$$A$$$ 的大小在每次操作后都会增加 $$$1$$$。
我们将多重集 $$$A$$$ 的余额定义为 $$$\max(a_i) - \min(a_i)$$$。在执行任意数量(可能为零)的操作后找到最小可能的余额。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。
每个测试用例的第二行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m \le 5 \cdot 10^6$$$) - 多重集的初始大小和元素的最大值。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) - 初始多重集中的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$,所有测试用例的 $$$m$$$ 总和不超过 $$$5 \cdot 10^6$$$。
输出
对于每个测试用例,打印一个整数——可能的最小余额。
示例
输入 #1
4 5 10 2 4 2 4 2 3 50 12 2 3 2 40 6 35 2 5 1 5
输出 #1
0 1 2 4
注意
在第一个测试用例中,我们可以对 $$$4$$$ 中的每一个应用 $$$(p,q) = (2,2)$$$ 的操作,并使多重集 $$$\{2,2,2,2,2,2,2\}$$$ 具有余额 $$$\max(\{2,2,2,2,2,2,2\}) - \min(\{2,2,2,2,2,2,2\}) = 0$$$。显然我们不能使这个余额低于$$$0$$$。
在第二个测试用例中,我们可以对 $$$12$$$ 应用操作 $$$(p,q) = (3,4)$$$。之后我们的多重集将是$$$\{3,4,2,3\}$$$。我们可以对 $$$4$$$ 再进行一次操作,$$$(p,q) = (2,2)$$$,使得多重集 $$$\{3,2,2,2,3\}$$$ 的余额等于 $$$1$$$。
在第三个测试用例中,我们可以对 $$$35$$$ 应用操作 $$$(p,q) = (5,7)$$$。最终的多重集是 $$$\{6,5,7\}$$$,余额等于 $$$7-5 = 2$$$。
在第四个测试用例中,我们无法应用任何操作,因此余额为 $$$5 - 1 = 4$$$。