CF1764B.Doremy's Perfect Math Class

"Everybody! Doremy's Perfect Math Class is about to start! Come and do your best if you want to have as much IQ as me!" In today's math class, Doremy is teaching everyone subtraction. Now she gives you a quiz to prove that you are paying attention in class.

You are given a set $S$ containing positive integers. You may perform the following operation some (possibly zero) number of times:

• choose two integers $x$ and $y$ from the set $S$ such that $x \gt y$ and $x - y$ is not in the set $S$.
• add $x-y$ into the set $S$.

You need to tell Doremy the maximum possible number of integers in $S$ if the operations are performed optimally. It can be proven that this number is finite.

“大家好！多蕾米的完美数学课马上就要开始啦！想拥有和我一样高的智商，就快来大展身手吧！”
在今天的数学课上，多蕾米正在教大家减法。现在她出了一道小测验，来检验你是否认真听讲。

给你一个包含正整数的集合 $S$。你可以执行以下操作若干次（可以为零次）：

• 从集合 $S$ 中选出两个整数 $x$ 和 $y$，满足 $x \gt y$，且 $x - y$ 不在集合 $S$ 中；
• 将 $x-y$ 加入集合 $S$。

你需要告诉多蕾米：若以最优方式执行上述操作，集合 $S$ 中最多可能包含多少个整数？可以证明该最大值是有限的。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line contains an integer $n$ ($2 \le n\le 10^5$) — the size of the set $S$.

The second line contains $n$ integers $a_1,a_2,\dots,a_n$ ($1\le a_1 \lt a_2 \lt \cdots \lt a_n \le 10^9$) — the positive integers in $S$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

输入包含多个测试用例。第一行包含一个整数 $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 \lt a_2 \lt \cdots \lt a_n \le 10^9$），即集合 $S$ 中的正整数。

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

For each test case, you need to output the maximum possible number of integers in $S$. It can be proven that this value is finite.

对于每个测试用例，你需要输出集合 $S$ 中可能包含的整数的最大数量。可以证明该值是有限的。

In the first test case, no such $x$ and $y$ exist. The maximum possible number of integers in $S$ is $2$.

In the second test case,

• $S={5,10,25}$ at first. You can choose $x=25$, $y=10$, then add $x-y=15$ to the set.
• $S={5,10,15,25}$ now. You can choose $x=25$, $y=5$, then add $x-y=20$ to the set.
• $S={5,10,15,20,25}$ now. You can not perform any operation now.

After performing all operations, the number of integers in $S$ is $5$. It can be proven that no other sequence of operations allows $S$ to contain more than $5$ integers.

在第一个测试用例中，不存在满足条件的 $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$ 个整数。