Cho một dãy \(A\) gồm \(N\) phần tử gồm các số nguyên dương \(A_1, A_2, ..., A_N\). Dãy \(C\) được gọi là dãy con BeautiQ độ dài \(K\) của \(A\) nếu tồn tại dãy chỉ số thoả mãn các điều kiện như sau:

• \(K \geq 1\).
• \(1 \leq i_1 < i_2 < i_3 < ... < i_K \leq N\).
• \(C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}\).
• \(C_1 < C_2 < ... < C_K\) nếu \(K \geq 2\).
• \(GCD(C_1, C_2) > 1\), \(GCD(C_2, C_3) > 1\), \(...,\) \(GCD(C_{K-1}, C_K) > 1\) nếu \(K \geq 2\). (\(GCD\) tương ứng với \(UCLN\))

Yêu cầu: Tìm độ dài \(K\) lớn nhất có thể của dãy con BeautiQ \(C\).

Input

• Dòng thứ nhất chứa số nguyên dương \(N\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_N\).

Output

• In ra số duy nhất là số nguyên dương \(K\).

Constraints

• \(N\leq 10^5\)
• \(A_i \leq 10^6\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^5\), \(A_i < A_{i+1}\) với \(\forall{i}, 1 \leq i < N\)
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm

Example

6
9 4 5 8 7 6 

2