← 返回题目列表

Codeforces · 2115/A

A. 水母和火焰牡丹

中文机器翻译题面 查看原题

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

Gellyfish 被赋予一个由 $$$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)$$$。

现在,Gellyfish 要求您提供实现她的目标所需的最少操作次数。

可以证明,水母总能达到她的目的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。

输出

对于每个测试用例,输出一个整数——实现目标的最小操作数。

示例

输入
复制

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$$$,则 $$$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]$$$。