CF2115A.Gellyfish and Flaming Peony

Gellyfish hates math problems, but she has to finish her math homework:

Gellyfish is given an array of $n$ positive integers $a_1, a_2, \ldots, a_n$.

She needs to do the following two-step operation until all elements of $a$ are equal:

1. Select two indexes $i$, $j$ satisfying $1 \leq i, j \leq n$ and $i \neq j$.
2. Replace $a_i$ with $\gcd(a_i, a_j)$.

Now, Gellyfish asks you for the minimum number of operations to achieve her goal.

It can be proven that Gellyfish can always achieve her goal.

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

水母得到了一个由 $n$ 个正整数组成的数组 $a_1, a_2, \ldots, a_n$。

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

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

现在，水母请你求出达成目标所需的最少操作次数。

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

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 5000$) — the length of the array.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq 5000$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 5000$）。随后是各测试用例的描述。

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

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

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

For each test case, output a single integer — the minimum number of operations to achieve her goal.

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

In the first test case, the following is a way that minimizes the number of operations:

1. Choose $i = 3$ and $j=2$ and replace $a_3$ with $\gcd(a_3,a_2) = \gcd(30, 20) = 10$, then $a$ becomes $[12, 20, 10]$.
2. Choose $i=1$ and $j=3$ and replace $a_1$ with $\gcd(a_1,a_3) = \gcd(12, 10) = 2$, then $a$ becomes $[2, 20, 10]$.
3. Choose $i=2$ and $j=1$ and replace $a_2$ with $\gcd(a_2,a_1) = \gcd(20, 2) = 2$, then $a$ becomes $[2, 2, 10]$.
4. Choose $i=3$ and $j=1$ and replace $a_3$ with $\gcd(a_3,a_1) = \gcd(10, 2) = 2$, then $a$ becomes $[2, 2, 2]$.

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

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