← 返回题目列表

Codeforces · 1419/C

C. 扫兴

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

一位名为 Killjoy 的新特工发明了一种病毒 COVID-2069,该病毒会感染 Codeforces 上的帐户。每个帐户都有一个评级,用整数描述(可能是负数或非常大)。

Killjoy 的帐户已被感染,评级为 $$$x$$$。它的评级是恒定的。除了她的账户外,还有$$$n$$$个账户,编号从$$$1$$$到$$$n$$$。第 $$$i$$$ 个帐户的初始评级为 $$$a_i$$$。任何受感染的帐户(最初唯一受感染的帐户是 Killjoy 的帐户)如果评级相同,就会立即感染任何未受感染的帐户。这可以在每次比赛开始时(在任何评级更改之前)和之后发生。如果帐户被感染,则无法治愈。

Codeforces 上定期举办竞赛。在每次竞赛中,任何 $$$n$$$ 帐户(包括受感染的帐户)都可以参加。 Killjoy 不能参加。每次比赛后,评分都会以这种方式更改:每个参与者的评分都会更改一个整数,但所有更改的总和必须等于零。新的评级可以是任何整数。

找出感染所有帐户所需的最少比赛次数。您可以选择哪些帐户将参加每次比赛以及评级如何变化。

可以证明,在有限次数的比赛中,所有账户都可以被感染。

输入

第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 100)$$$ — 测试用例的数量。接下来的 $$$2t$$$ 行包含所有测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$2 \le n \le 10^3$$$, $$$-4000 \le x \le 4000$$$) - Codeforces 上的帐户数量和 Killjoy 帐户的评级。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ $$$(-4000 \le a_i \le 4000)$$$ —其他帐户的评分。

输出

对于每个测试用例,输出感染所有帐户所需的最少竞赛数量。

示例

输入 #1

3
2 69
68 70
6 4
4 4 4 4 4 4
9 38
-21 83 50 -59 -77 15 -71 -78 20

输出 #1

1
0
2

注意

在第一个测试用例中,可以使所有评级等于 $$$69$$$。第一个帐户的评级将增加 $$$1$$$,第二个帐户的评级将减少 $$$1$$$,因此所有更改的总和将等于零。

在第二个测试用例中,所有帐户都将立即被感染,因为所有评级(包括 Killjoy 帐户的评级)都等于 $$$4$$$。