Nghi thức kho báu vàng

Trong một vương quốc cổ đại, có một kho báu được chia thành nhiều ngăn, mỗi ngăn chứa một số lượng vàng khác nhau. Số lượng vàng trong mỗi ngăn được biểu diễn bởi dãy số \(a\).

Để mở được kho báu, người thừa kế phải thực hiện một nghi thức đặc biệt. Trong mỗi nghi thức, số lượng vàng trong mỗi ngăn sẽ được thay đổi bằng ước số chung lớn nhất của số vàng trong ngăn đó và ngăn bên cạnh (ngăn bên cạnh ngăn cuối cùng là ngăn đầu tiên).

Ví dụ, nếu \(a = [16,24,10,5]\) thì sau một nghi lễ \(a\) mới \(=[gcd(16,24),\ gcd(24,10),\ gcd(10,5),\ gcd(5,16)] =[8,2,5,1]\).

Nghi thức này được lặp đi lặp lại cho đến khi số lượng vàng trong tất cả các ngăn trở nên bằng nhau. Ít nhất cần thực hiện bao nhiêu nghi thức để mở được kho báu?

Input

• Dòng đầu tiên chứa số nguyên dương \(t\) \((1 \leq t \leq 10^4)\) biểu thị số lượng bộ câu hỏi.
• Dòng đầu tiên của mỗi bộ câu hỏi, chứa số nguyên dương \(n\) \((2 \leq n \leq 2 \times 10^5)\) biểu thị số lượng ngăn.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) \((1 \leq a_i \leq 10^6)\) biểu thị số lượng vàng ban đầu trong mỗi ngăn.
• Tổng \(n\) qua các bộ câu hỏi không vượt quá \(2 \times 10^5\).

Output

• In ra \(t\) số nguyên là số bước cần thiết để mở kho báu tương ứng với mỗi bộ câu hỏi.

Example

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

Scoring

• \(30\%\) số test có \(n\) và tổng \(n \leq 1000\), kết quả luôn \(\leq 10000\).
• \(30\%\) số test có \(n\) và tổng \(n \leq 5 \times 10^4\).
• \(40\%\) số test có \(n\) và tổng \(n \leq 2 \times 10^5\).