← 返回题目列表

Codeforces · 1777/C

C. 测验大师

中文机器翻译题面 查看原题

学校必须决定参加国际测验的团队。学校有 $$$n$$$ 名学生。我们可以使用数组 $$$a$$$ 来描述学生,其中 $$$a_i$$$ 是第 $$$i$$$ ($$$1 \le i \le n$$$) 学生的聪明程度。

共有 $$$m$$$ 个主题 $$$1, 2, 3, \ldots, m$$$ 组成测验问题。如果 $$$(a_i \bmod T) = 0$$$,则第 $$$i$$$ 学生被认为精通某个主题 $$$T$$$。否则的话,他在这个话题上还是个菜鸟。

如果对于每个主题都有一个精通该主题的团队成员,我们就说一个学生团队集体精通所有主题。

找到一个集体精通所有主题的团队,使得该团队中任何两个学生的聪明才智之间的最大差异最小化。输出这个差值。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含 $$$n$$$ 和 $$$m$$$ ($$$1 \le n,m \le 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

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

输出

对于每个测试用例,将答案打印在新行上。如果无解,则输出$$$-1$$$。

示例

输入 #1

3
2 4
3 7
4 2
3 7 2 9
5 7
6 4 3 5 7

输出 #1

-1
0
3

注意

在第一个测试用例中,我们的参与者的聪明程度为 $$$3$$$ 和 $$$7$$$,并且 $$$m = 4$$$。因此,没有一个学生的聪明程度可以被$$$2$$$整除。由于 $$$2 \leq m$$$,因此无法选择团队。

在第二个测试用例中,我们可以选择聪明程度 $$$2$$$ 的参与者作为团队中唯一的参与者。这样,团队将共同精通 $$$1$$$ 和 $$$2$$$ 这两个主题。

在第三个测试用例中,考虑参与者聪明程度为 $$$4, 5, 6, 7$$$ 的团队。这样,团队将集体精通所有主题 $$$1, 2, \ldots, 7$$$。