← 返回题目列表

Codeforces · 1547/F

F. 阵列稳定(GCD 版本)

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

给定一个正整数数组 $$$a = [a_0, a_1, \dots, a_{n - 1}]$$$ ($$$n \ge 2$$$)。

在一个步骤中,数组 $$$a$$$ 被另一个长度为 $$$n$$$ 的数组替换,其中每个元素是两个相邻元素(元素本身及其右邻居;考虑第 $$$(n - 1)$$$ 元素的右邻居是第 $$$0$$$ 元素)。

正式来说,一个新数组 $$$b = [b_0, b_1, \dots, b_{n - 1}]$$$ 正在从数组 $$$a = [a_0, a_1, \dots, a_{n - 1}]$$$ 构建,使得 $$$b_i$$$ $$$= \gcd(a_i, a_{(i + 1) \mod n})$$$,其中$$$\gcd(x, y)$$$是$$$x$$$和$$$y$$$的最大公约数,$$$x \mod y$$$是$$$x$$$除以$$$y$$$的余数。在一个步骤中,数组 $$$b$$$ 被构建,然后数组 $$$a$$$ 被 $$$b$$$ 替换(即,赋值 $$$a$$$ := $$$b$$$ 正在发生)。

例如,如果 $$$a = [16, 24, 10, 5]$$$,则 $$$b = [\gcd(16, 24)$$$, $$$\gcd(24, 10)$$$, $$$\gcd(10, 5)$$$, $$$\gcd(5, 16)]$$$ $$$= [8,2,5,1]$$$。因此,一步之后,数组 $$$a = [16, 24, 10, 5]$$$ 将等于 $$$[8, 2, 5, 1]$$$。

对于给定数组 $$$a$$$,找到所有值 $$$a_i$$$ 变得相等后的最小步数(即 $$$a_0 = a_1 = \dots = a_{n - 1}$$$)。如果原始数组 $$$a$$$ 由相同元素组成,则认为步数等于 $$$0$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。

每个测试用例包含两行。第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 序列 $$$a$$$ 的长度。第二行包含 $$$n$$$ 整数 $$$a_0, a_1, \dots, a_{n - 1}$$$ ($$$1 \le a_i \le 10^6$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

打印 $$$t$$$ 数字 — 每个测试用例的答案。

示例

输入 #1

5
4
16 24 10 5
4
42 42 42 42
3
4 6 4
5
1 2 3 4 5
6
9 9 27 9 9 63

输出 #1

3
0
2
1
1