CFCF2115A.Gellyfish and Flaming Peony

普及/提高-

官方

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

Gellyfish 讨厌数学题，但她必须完成她的数学作业：

Gellyfish 得到一个包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ 的数组。

她需要反复进行以下两步操作，直到数组 $a$ 的所有元素都相等为止：

现在，Gellyfish 想知道，最少需要多少次操作才能实现目标。

可以证明，Gellyfish 总是能够实现目标。

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

每个测试用例的第一行包含一个整数 $n$ （ $1 \leq n \leq 5000$ ），表示数组的长度。

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

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

对于每个测试用例，输出一个整数，表示实现目标所需的最小操作次数。

输入#1

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

输出#1

4
3
3

在第一个测试用例中，以下是一种最小化操作次数的方法：

选择 $i = 3$ ， $j = 2$ ，用 $\gcd(a_3,a_2) = \gcd(30, 20) = 10$ 替换 $a_3$ ，此时 $a$ 变为 $[12, 20, 10]$ 。
选择 $i = 1$ ， $j = 3$ ，用 $\gcd(a_1,a_3) = \gcd(12, 10) = 2$ 替换 $a_1$ ，此时 $a$ 变为 $[2, 20, 10]$ 。
选择 $i = 2$ ， $j = 1$ ，用 $\gcd(a_2,a_1) = \gcd(20, 2) = 2$ 替换 $a_2$ ，此时 $a$ 变为 $[2, 2, 10]$ 。
选择 $i = 3$ ， $j = 1$ ，用 $\gcd(a_3,a_1) = \gcd(10, 2) = 2$ 替换 $a_3$ ，此时 $a$ 变为 $[2, 2, 2]$ 。