A. 水母与火焰芍药

题目描述

水母讨厌数学问题，但她必须完成数学作业：

水母得到了一个包含 $n$ 个正整数的数组 $a_1, a_2, \dots, a_n$。

她需要重复执行以下两步操作，直到数组中的所有元素都相等：

1. 选择两个下标 $i, j$，满足 $1 \le i, j \le n$ 且 $i \ne j$。
2. 将 $a_i$ 替换为 $\gcd(a_i, a_j)$。

现在，水母询问你：为了达成目标，所需的最少操作次数是多少？

可以证明，水母总能达成目标。

输入格式

每个测试包含多个测试用例。
第一行包含一个整数 $t$（$1 \le t \le 5000$），表示测试用例的数量。
接下来是每个测试用例的描述：

• 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5000$），表示数组的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 5000$），表示数组的元素。

保证所有测试用例的 $n$ 之和不超过 $5000$。

输出格式

对于每个测试用例，输出一个整数 —— 达成目标所需的最少操作次数。

样例输入

3
3
12 20 30
6
1 9 1 9 8 1
3
6 14 15

样例输出

4
3
3

样例解释

第一个测试用例

一种能最小化操作次数的做法：

1. 选择 $i=3$，$j=2$，将 $a_3$ 替换为 $\gcd(a_3, a_2) = \gcd(30, 20) = 10$，数组变为 $[12, 20, 10]$。
2. 选择 $i=1$，$j=3$，将 $a_1$ 替换为 $\gcd(a_1, a_3) = \gcd(12, 10) = 2$，数组变为 $[2, 20, 10]$。
3. 选择 $i=2$，$j=1$，将 $a_2$ 替换为 $\gcd(a_2, a_1) = \gcd(20, 2) = 2$，数组变为 $[2, 2, 10]$。
4. 选择 $i=3$，$j=1$，将 $a_3$ 替换为 $\gcd(a_3, a_1) = \gcd(10, 2) = 2$，数组变为 $[2, 2, 2]$。

因此最少操作次数为 $4$。