水母讨厌数学题,但她必须完成她的数学作业:
Gellyfish 被赋予一个由 $$$n$$$ 正整数 $$$a_1, a_2, \ldots, a_n$$$ 组成的数组。
她需要执行以下两步操作,直到$$$a$$$的所有元素都相等:
- 选择两个索引 $$$i$$$、$$$j$$$ 满足 $$$1 \leq i、j \leq n$$$ 和 $$$i \neq j$$$。
- 将 $$$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$$$。
输出
对于每个测试用例,输出一个整数——实现目标的最小操作数。
示例
输入复制
3312 20 3061 9 1 9 8 136 14 15
输出复制
4 3 3
注意
在第一个测试用例中,以下是最小化操作次数的方法:
- 选择 $$$i = 3$$$ 和 $$$j=2$$$ 并将 $$$a_3$$$ 替换为 $$$\gcd(a_3,a_2) = \gcd(30, 20) = 10$$$,则 $$$a$$$ 变为 $$$[12, 20, 10]$$$。
- 选择 $$$i=1$$$ 和 $$$j=3$$$ 并将 $$$a_1$$$ 替换为 $$$\gcd(a_1,a_3) = \gcd(12, 10) = 2$$$,则 $$$a$$$ 变为 $$$[2, 20, 10]$$$。
- 选择 $$$i=2$$$ 和 $$$j=1$$$ 并将 $$$a_2$$$ 替换为 $$$\gcd(a_2,a_1) = \gcd(20, 2) = 2$$$,则 $$$a$$$ 变为 $$$[2, 2, 10]$$$。
- 选择 $$$i=3$$$ 和 $$$j=1$$$ 并将 $$$a_3$$$ 替换为 $$$\gcd(a_3,a_1) = \gcd(10, 2) = 2$$$,则 $$$a$$$ 变为 $$$[2, 2, 2]$$$。