Задан массив из положительных целых чисел $$$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$$$.