CF2115A Gellyfish and Flaming Peony

Gellyfish 讨厌数学题，但她必须完成她的数学作业： Gellyfish 得到一个包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ 的数组。 她需要反复进行以下两步操作，直到数组 $a$ 的所有元素都相等为止： 1. 选择两个下标 $i$、$j$，满足 $1 \leq i, j \leq n$ 且 $i \neq j$。 2. 用 $\gcd(a_i, a_j)$ 替换 $a_i$ 的值。 现在，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. 选择 $i = 3$，$j = 2$，用 $\gcd(a_3,a_2) = \gcd(30, 20) = 10$ 替换 $a_3$，此时 $a$ 变为 $[12, 20, 10]$。 2. 选择 $i = 1$，$j = 3$，用 $\gcd(a_1,a_3) = \gcd(12, 10) = 2$ 替换 $a_1$，此时 $a$ 变为 $[2, 20, 10]$。 3. 选择 $i = 2$，$j = 1$，用 $\gcd(a_2,a_1) = \gcd(20, 2) = 2$ 替换 $a_2$，此时 $a$ 变为 $[2, 2, 10]$。 4. 选择 $i = 3$，$j = 1$，用 $\gcd(a_3,a_1) = \gcd(10, 2) = 2$ 替换 $a_3$，此时 $a$ 变为 $[2, 2, 2]$。 由 ChatGPT 4.1 翻译