Ổn định mảng (phiên bản GCD)

Cho mảng số nguyên dương $a=[a_0,a_1,\dots ,a_{n-1}]$ (với $n\ge 2$).

Trong một bước, mảng $a$ được thay bằng mảng mới $b$ cùng độ dài $n$, trong đó mỗi phần tử là ước chung lớn nhất (GCD) của hai phần tử kề nhau theo nghĩa vòng tròn:

$$b_i=gcd(a_i,a_{(i+1)modn})$$

Tức là phần tử kề phải của $a_{n-1}$ chính là $a_0$. Sau khi tính xong $b$, ta gán $a:=b$.

Ví dụ, nếu $a=[16,24,10,5]$ thì $b=[gcd(16,24),gcd(24,10),gcd(10,5),gcd(5,16)]=[8,2,5,1]$.

Với mảng $a$ cho trước, hãy tìm số bước nhỏ nhất để tất cả phần tử của $a$ trở nên bằng nhau (tức $a_0=a_1=\cdots =a_{n-1}$). Nếu ngay từ đầu mảng đã có tất cả phần tử bằng nhau thì đáp án là $0$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ ($1\le t\le {10}^4$) — số bộ test.
• Mỗi bộ test gồm hai dòng:
  • Dòng đầu chứa $n$ ($2\le n\le 2·{10}^5$).
  • Dòng thứ hai chứa $n$ số nguyên $a_0,a_1,\dots ,a_{n-1}$ ($1\le a_i\le {10}^6$).

Tổng giá trị $n$ trên tất cả các bộ test không vượt quá $2·{10}^5$.

Dữ liệu ra

In ra $t$ số — mỗi dòng là đáp án cho một bộ test theo thứ tự đề bài.

Ví dụ