Dãy thân thiện

Một dãy số nguyên dương được gọi là dãy thân thiện nếu nó tăng ngặt và với hai phần tử đứng cạnh nhau bất kỳ thì ước chung lớn nhất của chúng lớn hơn \(1\) (dãy chỉ có một phần tử cũng là dãy thân thiện).

Cho dãy \(a_1, a_2, \dots, a_n\) đã được sắp xếp tăng ngặt. Nam muốn xoá ít nhất các phần tử sao cho dãy còn lại là dãy thân thiện. Hãy cho biết dãy thân thiện thu được có bao nhiêu phần tử (tức là độ dài lớn nhất của một dãy con thân thiện).

Input

• Dòng 1: số nguyên dương \(n\).
• Dòng 2: \(n\) số nguyên \(a_1 < a_2 < \dots < a_n\).

Output

• In ra số phần tử còn lại lớn nhất.

Constraints

• \(1 \le n \le 10^5\), \(1 \le a_i \le 10^5\).
• 40% số test: \(n \le 20\); 30% số test: \(n \le 1000\).

Sample Input

8
2 3 4 6 9 12 15 25

Sample Output

7

Explanation

Xoá số \(3\), giữ lại \(2,4,6,9,12,15,25\): các cặp kề nhau có ước chung lớn nhất lần lượt là \(2,2,3,3,3,5\), đều lớn hơn \(1\).