Cho số nguyên dương \(n\) và dãy số nguyên dương \(a_1,a_2,…,a_n\).

Cần chọn ra một số phần tử liên tiếp trong dãy \(a_1,a_2,…,a_n\) bắt đầu từ vị trí \(l\) đến vị trí \(r (1 ≤ l ≤ r ≤ n)\) sao cho:

• \(min⁡(a_l,a_{(l+1)},…,a_r ) =GCD(a_l,a_{(l+1)},…,a_r);\)

• \(r-l+1\) lớn nhất.

Với:

\(min⁡(a_l,a_{(l+1)},…,a_r )\) là số nhỏ nhất của \( a_l,a_{(l+1)},…,a_r\);

\(GCD(a_l,a_{(l+1)},…,a_r ) \) là ước chung lớn nhất của \( a_l,a_{(l+1)},…,a_r\)

Yêu cầu: Cho số nguyên dương \(n\) và dãy số nguyên dương \(a_1,a_2,…,a_n\). Hãy tìm giá trị \(r - l + 1\) lớn nhất thỏa mãn điều kiện trên.

Input

• Dòng thứ nhất chứa số nguyên dương \(n (n ≤ 10^2 )\);

• Dòng thứ hai chứa n ố nguyên dương \(a_1,a_2,…,a_n (1≤a_i ≤10^6,1≤i≤n).\)

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Output

• Ghi ra giá trị r-l+1 lớn nhất thỏa điều kiện bài toán.

Sample Input

7
14 13 6 18 12 6 9

Sample Output

4