Số nguyên tố là số nguyên dương lớn hơn ~1~ và chỉ có hai ước dương là ~1~ và chính nó.

Ví dụ: ~2, 3, 7, 13~ là các số nguyên tố còn ~4, 6, 20~ không là số nguyên tố.

Khôi đang học về số nguyên tố. Hôm nay, thầy giáo cho một dãy số nguyên dương ~A~ gồm ~n~ phần tử ~A_1, A_2, …, A_n~ và yêu cầu Khôi đếm số lượt đổi chỗ ít nhất các phần tử của dãy ~A~ để tất cả các số nguyên tố trong dãy được gom vào một miền liên tiếp.

Em hãy giúp Khôi tìm ra đáp án của bài toán nhé!

Input

Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~.

Dòng tiếp theo chứa n số nguyên dương ~A_1, A_2, …, A_n~, giữa hai số cách nhau một khoảng trắng ~(1 \le A_i \le 10^9)~.

Output

Một số nguyên dương duy nhất là số lượng đổi chỗ ít nhất để được miền nguyên tố lớn nhất.

Sample Input

7
10 2 3 6 78 5

Sample Output

1

Giải thích

Đổi chỗ số ~6~ và số ~5~ để các số nguyên tố được gom vào một miền duy nhất.

Subtask

• Có ~50\%~ test có ~n \le 10^3, A_i \le 10^3~.

• Có ~30\%~ test có ~n \le 10^4, Ai \le 10^5~.

• Có ~20\%~ test có giới hạn như trong đề.