Array-Gift

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

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

Sample Input

2
4
2 3 5 7
4
2 4 6 8

Sample Output

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$ 次操作，可以证明这是最少可能的操作次数。

Source

2024“钉耙编程”中国大学生算法设计超级联赛（5）