题目描述

“大家好！Doremy 的完美数学课马上就要开始了！如果你想拥有和我一样高的智商，就来尽力表现吧！”在今天的数学课上，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 \times 10^5$。

输出格式

对于每组测试数据，输出集合 $S$ 最多可以包含多少个整数。可以证明，这个值是有限的。

说明/提示

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

由 ChatGPT 4.1 翻译

样例

2
2
1 2
3
5 10 25

2
5