Miền nguyên tố

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,\dots ,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. Mỗi lượt đổi chỗ chọn hai phần tử bất kỳ của dãy (không nhất thiết đứng cạnh nhau) và đổi chỗ chúng cho nhau.

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

Dữ liệu vào

• 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,\dots ,A_n$, giữa hai số cách nhau một khoảng trắng $(1\le A_i\le {10}^9)$.

Dữ liệu ra

Một số nguyên duy nhất là số lượt đổi chỗ ít nhất để tất cả các số nguyên tố trong dãy nằm trong một miền liên tiếp. Nếu các số nguyên tố đã nằm liên tiếp nhau (hoặc dãy không có số nguyên tố nào) thì in ra $0$.

Ràng buộc

• $1\le n\le {10}^5$.
• $1\le A_i\le {10}^9$.

Subtasks

• Có $50\%$ số test có $n\le {10}^3$, $A_i\le {10}^3$.
• Có $30\%$ số test có $n\le {10}^4$, $A_i\le {10}^5$.
• Có $20\%$ số test có giới hạn như trong đề.

Ví dụ