Problem Description

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

- 操作1：选择不同的下标 $i,j$（即 $1\leq i,j\leq n$，$i \neq j$），且 $a_j\neq 0$，然后将 $a_i $ 修改为 $ a_{i} \bmod a_{j} $
- 操作2：选择某个 $i$ 满足 $1 \leq i \leq n$ 和任意一个 **正整数** $x$ ,将 $a_{i} $ 修改为 $a_{i}+x$.

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

Input

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

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

Output

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

2
4
2 3 5 7
4
2 4 6 8

4
3

Hint

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

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