Dãy số gồm các số nguyên dương được gọi là dãy số thân thiện nếu nó là một dãy tăng dần và hai phần tử đứng cạnh nhau có ước chung lớn nhất là \(1\).

Nam thực hiện xoá ít nhất các phần tử của dãy \(A_1,A_2...A_N\) để các phần tử còn lại tạo thành dãy số thân thiện. Bạn hãy xác định giúp Nam số lượng phần tử của dãy thân thiện Nam thu được.

Dãy con của một dãy là dãy có thể đạt được bằng cách xoá đi một số phần tử trong dãy ban đầu.

Dữ liệu vào

• Dòng \(1\) là số nguyên dương \(N\) \((1 \le N \le 1000)\)
• Dòng tiếp theo ghi dãy số \(A_1,A_2...A_N\) theo thứ tự tăng dần \((1 \le A_i \le 10^9)\)

Dữ liệu ra

• Ghi ra một số nguyên duy nhất là đáp án của bài.

Input 1

5
2 3 4 6 9

Output 1

4