F. Стабилизируй массив (НОД-версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив из положительных целых чисел $$$a = [a_0, a_1, \dots, a_{n - 1}]$$$ ($$$n \ge 2$$$).

За один шаг массив $$$a$$$ заменяется на другой массив длины $$$n$$$, в котором каждый элемент это наибольший общий делитель (НОД) двух соседних элементов (самого элемента и его правого соседа; считайте, что правый сосед $$$(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$$$.

Входные данные

В первой строке записано целое число $$$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$$$ чисел — ответы на наборы входных данных теста.

Пример
Входные данные
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
Выходные данные
3
0
2
1
1