“大家！一锐的完美数学课即将开始！如果你想拥有和我一样多的智商，那就来尽力而为吧！在今天的数学课上，一锐正在教大家减法。现在他给你一个测验，证明你在课堂上专心。你得到一个包含正整数的集合 S。您可以执行以下操作几次（可能为零次）：从集合 S 中选择两个整数 x 和 y，当 x>y 并且 x−y 不在集合 S 中，将 x−y 添加到集合 S 中。如果操作以最佳方式执行，您需要告诉一锐S 中最大可能的整数个数。可以证明这个数字是有限的。

输入由多个测试用例组成。第一行包含一个整数 t （1≤t≤10^4） — 测试用例的数量。测试用例的说明如下。

第一行包含一个整数 n （2≤n≤10^5） — 集合 S 的大小。

第二行包含 n 个整数 a1，a2,...,an （1≤a1<a2<⋯<an≤10^9） — S 中的正整数。

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

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

GJ2022