“大家!多米的完美数学课即将开始!如果你想拥有和我一样高的智商,就来加油吧!”今天的数学课,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$$$ 整数。