← 返回题目列表

Codeforces · 1307/B

B. 牛和朋友

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

贝西有太多的朋友,因为她是每个人最喜欢的牛!她的新朋友兔子正试图跳过去,这样他们就可以玩了!

更具体地说,他希望通过多次跳跃从 $$$(0,0)$$$ 到达 $$$(x,0)$$$。仅当跳跃端点之间的欧几里得距离是其最喜欢的数字之一:$$$a_1、a_2、\ldots、a_n$$$ 时,他才愿意从 2D 平面上的一个点跳跃到另一点。 Rabbit 从 $$$(0,0)$$$ 到 $$$(x,0)$$$ 需要经过多少跳?兔子可能会落在坐标非整数的点上。可以证明兔子总能到达目的地。

回想一下,$$$(x_i, y_i)$$$ 和 $$$(x_j, y_j)$$$ 之间的欧几里德距离是 $$$\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$$$。

例如,如果 Rabbit 最喜欢的数字 $$$1$$$ 和 $$$3$$$,他可以从 $$$(0,0)$$$ 跳两跳到 $$$(4,0)$$$,如下所示。请注意,还存在其他有效方法可以在 $$$2$$$ 跃点中跳转到 $$$(4,0)$$$(例如 $$$(0,0)$$$ $$$\rightarrow$$$ $$$(2,-\sqrt{5})$$$ $$$\rightarrow$$$ $$$(4,0)$$$)。

这是第一个示例的图形。两次跳跃的距离都是$$$3$$$,这是兔子最喜欢的数字之一。

换句话说,每次 Rabbit 选择某个数字 $$$a_i$$$ 并以等于 $$$a_i$$$ 的距离向他想要的任何方向跳跃。同一号码可以多次使用。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。接下来的 $$$2t$$$ 行包含测试用例 - 每个测试用例两行。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le x \le 10^9$$$) — 分别是 Rabbit 最喜欢的数字的数量和想要旅行的距离。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — Rabbit 最喜欢的数字。保证最喜欢的号码是不同的。

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

输出

对于每个测试用例,打印一个整数 - 所需的最小跃点数。

示例

输入 #1

4
2 4
1 3
3 12
3 4 5
1 5
5
2 10
15 4

输出 #1

2
3
1
2

注意

样本的第一个测试用例如上图所示。兔子可以跳到 $$$(2,\sqrt{5})$$$,然后跳到 $$$(4,0)$$$,总共跳两跳。每跳的距离为 $$$3$$$,这是他最喜欢的数字之一。

在示例的第二个测试用例中,Rabbit 跳跃 $$$3$$$ 次的一种方法是:$$$(0,0)$$$ $$$\rightarrow$$$ $$$(4,0)$$$ $$$\rightarrow$$$ $$$(8,0)$$$ $$$\rightarrow$$$ $$$(12,0)$$$。

在示例的第三个测试用例中,Rabbit 可以从 $$$(0,0)$$$ 跳到 $$$(5,0)$$$。

在示例的第四个测试用例中,Rabbit 可以跳跃:$$$(0,0)$$$ $$$\rightarrow$$$ $$$(5,10\sqrt{2})$$$ $$$\rightarrow$$$ $$$(10,0)$$$。