Dãy con liên kết ước chung

Cho dãy số nguyên dương \(a_1 < a_2 < \dots < a_n\) (dãy tăng ngặt). Ta gọi một dãy con (giữ nguyên thứ tự, bỏ bớt một số phần tử) là liên kết nếu hai phần tử đứng cạnh nhau của nó luôn có ước chung lớn nhất lớn hơn \(1\). Dãy con chỉ có một phần tử luôn là liên kết.

Hãy xác định độ dài lớn nhất của một dãy con liên kết của \(a\).

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, \dots, a_n\) theo thứ tự tăng dần ngặt.

Output

• In ra một số nguyên: độ dài lớn nhất tìm được.

Constraints

• \(1 \le n \le 10^5\)
• \(1 \le a_i \le 10^6\)
• \(a_1 < a_2 < \dots < a_n\)

Sample Input

8
6 7 9 10 14 15 21 25

Sample Output

4

Explanation

Chọn \(6, 10, 14, 21\): các ước chung lớn nhất của các cặp kề lần lượt là \(2, 2, 7\), đều lớn hơn \(1\). Không có dãy liên kết nào dài hơn \(4\).