← 返回题目列表

Codeforces · 1764/B

B. 多蕾米的完美数学课

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

“大家!多米的完美数学课即将开始!如果你想拥有和我一样高的智商,就来加油吧!”今天的数学课,Doremy正在教大家减法。现在她给你一个测验来证明你在课堂上专心听讲。

给你一个包含正整数的集合$$$S$$$。您可以执行以下操作几次(可能为零):

- 从集合 $$$S$$$ 中选择两个整数 $$$x$$$ 和 $$$y$$$,使得 $$$x > y$$$ 和 $$$x - y$$$ 不在集合 $$$S$$$ 中。
- 将 $$$x-y$$$ 添加到集合 $$$S$$$ 中。

如果运算执行最佳,您需要告诉 Doremy $$$S$$$ 中整数的最大可能数量。可以证明这个数是有限的。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

第一行包含一个整数 $$$n$$$ ($$$2 \le n\le 10^5$$$) — 集合 $$$S$$$ 的大小。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\dots,a_n$$$ ($$$1\le a_1 < a_2 < \cdots < a_n \le 10^9$$$) — $$$S$$$ 中的正整数。

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

输出

对于每个测试用例,您需要输出 $$$S$$$ 中最大可能的整数个数。可以证明这个值是有限的。

示例

输入 #1

2
2
1 2
3
5 10 25

输出 #1

2
5

注意

在第一个测试用例中,不存在这样的 $$$x$$$ 和 $$$y$$$ 。 $$$S$$$ 中整数的最大可能数量是 $$$2$$$。

在第二个测试用例中,

- 首先$$$S=\{5,10,25\}$$$。您可以选择 $$$x=25$$$、$$$y=10$$$,然后将 $$$x-y=15$$$ 添加到集合中。
- $$$S=\{5,10,15,25\}$$$ 现在。您可以选择 $$$x=25$$$、$$$y=5$$$,然后将 $$$x-y=20$$$ 添加到集合中。
- $$$S=\{5,10,15,20,25\}$$$ 现在。您现在无法执行任何操作。

执行完所有操作后,$$$S$$$ 中的整数个数为$$$5$$$。可以证明,没有其他操作序列允许 $$$S$$$ 包含超过 $$$5$$$ 整数。