题目描述

张旭锋做梦梦到要教大家减法。现在他给大家一个测验，以证明你在课堂上的注意力。

给你一个包含正整数的集合s。你可以进行如下操作，次数可能为零。

从集合s中选择两个整数x和y，使得x>y且x-y不在集合s中。

将x-y加入到集合s中。

你需要告诉张旭锋（如果不告诉他，他会把你踢出acm社），如果以最佳方式进行运算，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中可能存在的最大正整数数量。可以证明，这个值是有限的。

2
2
1 2
3
5 10 25

2
5

提示