Dãy con nguyên tố kề nhau

Cho dãy số nguyên dương \(A_1 < A_2 < \dots < A_N\) (dãy tăng ngặt). Một dãy con của \(A\) (giữ nguyên thứ tự, bỏ đi một số phần tử) được gọi là hợp lệ nếu hai phần tử đứng cạnh nhau trong dãy con luôn có ước chung lớn nhất bằng \(1\). Dãy con chỉ có một phần tử luôn được coi là hợp lệ.

Hãy tìm độ dài lớn nhất của một dãy con hợp lệ.

Input

• Dòng đầu chứa số nguyên dương \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \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 của dãy con hợp lệ.

Constraints

• \(1 \le N \le 1000\)
• \(1 \le A_i \le 10^9\)
• \(A_1 < A_2 < \dots < A_N\)

Sample Input

7
3 4 6 8 9 15 16

Sample Output

4

Explanation

Có thể chọn dãy con \(3, 4, 9, 16\): các cặp kề \((3,4)\), \((4,9)\), \((9,16)\) đều có \(\gcd = 1\). Không thể chọn dãy dài hơn.