CF1547F.Array Stabilization (GCD version)

You are given an array of positive integers $a = [a_0, a_1, \dots, a_{n - 1}]$ ($n \ge 2$).

In one step, the array $a$ is replaced with another array of length $n$, in which each element is the greatest common divisor (GCD) of two neighboring elements (the element itself and its right neighbor; consider that the right neighbor of the $(n - 1)$-th element is the $0$-th element).

Formally speaking, a new array $b = [b_0, b_1, \dots, b_{n - 1}]$ is being built from array $a = [a_0, a_1, \dots, a_{n - 1}]$ such that $b_i$ $= \gcd(a_i, a_{(i + 1) \mod n})$, where $\gcd(x, y)$ is the greatest common divisor of $x$ and $y$, and $x \mod y$ is the remainder of $x$ dividing by $y$. In one step the array $b$ is built and then the array $a$ is replaced with $b$ (that is, the assignment $a$ := $b$ is taking place).

For example, if $a = [16, 24, 10, 5]$ then $b = [\gcd(16, 24)$, $\gcd(24, 10)$, $\gcd(10, 5)$, $\gcd(5, 16)]$ $= [8, 2, 5, 1]$. Thus, after one step the array $a = [16, 24, 10, 5]$ will be equal to $[8, 2, 5, 1]$.

For a given array $a$, find the minimum number of steps after which all values $a_i$ become equal (that is, $a_0 = a_1 = \dots = a_{n - 1}$). If the original array $a$ consists of identical elements then consider the number of steps is equal to $0$.

给你一个正整数数组 $a = [a_0, a_1, \dots, a_{n - 1}]$（其中 $n \ge 2$）。

每一步操作中，数组 $a$ 被替换为另一个长度为 $n$ 的数组，其中每个元素是其自身与其右侧相邻元素的最大公约数（GCD）；特别地，第 $(n - 1)$ 个元素的右侧相邻元素定义为第 $0$ 个元素。

形式化地，由数组 $a = [a_0, a_1, \dots, a_{n - 1}]$ 构造新数组 $b = [b_0, b_1, \dots, b_{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$。

The first line contains an integer $t$ ($1 \le t \le 10^4$). Then $t$ test cases follow.

Each test case contains two lines. The first line contains an integer $n$ ($2 \le n \le 2 \cdot 10^5$) — length of the sequence $a$. The second line contains $n$ integers $a_0, a_1, \dots, a_{n - 1}$ ($1 \le a_i \le 10^6$).

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

Print $t$ numbers — answers for each test case.

输出 $t$ 个数字——每个测试用例的答案。