J-诺艾儿与圣光爆发_哈尔滨理工大学2025年国庆新生赛第一场

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在Alice In Cradle的世界里，诺艾儿是出身于正统精灵的炼金术师的家系中分出的柯涅尔家族的后裔，是精灵和兽人的混血。

在该游戏中，圣光爆发不仅仅可以挣脱boss的狂暴控制。在爆发后的0.5秒左右的时间内诺艾儿将处于无敌状态，并且立刻重置所有的角色动作和魔法充能，消除几乎全部的异常状态!

想要成为一名优秀的魔法师，诺艾儿必须掌握圣光爆发这个技能。

为了更快的学会圣光爆发，诺艾儿找到老师普莉姆拉，希望能进行特训。
普莉姆拉给诺艾儿出了一道题，只要诺艾儿能完成，就可以获得圣光爆发这个技能。

假定诺艾儿有一个由 $n$ 个正整数 $a_1, a_2, \cdots, a_n$ 组成的数组。

在数组 $a$ 的所有元素相等之前，她需要进行以下两步操作：
1. 选择两个索引 $i$ 、 $j$ ，满足 $1\leq i, j\leq n$ 且 $i\neq j$ 。
2. 将 $a_i$ 替换为 $\gcd(a_i, a_j)$ 。

现在，试问诺艾儿达到目标所需的最少操作次数。

可以证明诺艾儿总能达成目标。

输入描述:

每个测试包含多个测试用例。第一行包含测试用例的数量  （ ）。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数  （  ）——数组的长度。

每个测试用例的第二行包含  个整数 （  ）——数组的元素。

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

输出描述:

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

示例1

输入

复制

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

输出

复制

4
3
3