“大家注意啦！哆来咪的完美数学课马上就要开始了！如果你想拥有和我一样高的智商，就快来展现你的实力吧！”在今天的数学课上，哆来咪正在教大家减法。现在她给你出了一个测验，来证明你在课堂上认真听讲了。

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

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

你需要告诉哆来咪，如果以最优方式进行操作，集合 $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 < \dots < 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 个整数。