最近开始流行赠送数组，所以 Beijixing 送给了 Liyishui 一个长度为 $n$ 的正整数序列 $a=[a_1,…,a_n]$，并附赠了两种操作：

• 操作1：选择不同的下标 $i,j$（即 $1≤i,j≤n，i≠j$），且 $a_j≠0$，然后将 $a_i$ 修改为 $a_i\ mod\ a_j$
• 操作2：选择某个 $i$ 满足 $1≤i≤n$ 和任意一个 正整数 $x$ ,将 $a_i$ 修改为 $a_i+x$.

Liyishui 喜欢倒腾数组，她希望只使用这两种操作让 $a$ 只剩 恰好一个 非 $0$ 数，其他的数都变成 $0$。两种操作均可使用任意次。不幸的是Liyishui最近忙着赶ddl，你能帮忙求出最小操作次数吗？

第一行输入一个正整数 $T$ ,表示一共有 $T$ 组测试用例，$1≤T≤30$.

接下来每组测试用例由两行构成：其中第一行输入一个正整数 $n(1≤n≤100)$ ，表示序列 $a$ 的长度。第二行输入 $n$ 个正整数 $a_1,…,a_n$，相邻两数用一个空格隔开，表示序列 $a$ .
对 $1≤i≤n$ ，有 $1≤a_i≤10^6$ .

对每个测试用例，输出一行一个整数，表示最小操作次数。

对于第一个样例，一种可能操作如下：$[2,3,5,7]→[2,1,5,7]→[0,1,5,7]→[0,1,0,7]→[0,1,0,0]$，
一共用了 $4$ 次操作，可以证明这是最少可能的操作次数。

对于第二个样例，一种可能操作如下：$[2,4,6,8]→[2,0,6,8]→[2,0,0,8]→[2,0,0,0]$，
一共用了 $3$ 次操作，可以证明这是最少可能的操作次数。