Trái Đất vào năm \(14789654\), số nguyên tố được ưa chuộng đến mức chính phủ dùng nó để đánh giá thực lực của mỗi người.

Cụ thể: Mỗi người sẽ được chính phủ cấp cho \(𝑀\) số nguyên dương, số thứ \(i\) nhận giá trị \(a[i]\) (hoặc \(a[i]=1\) hoặc \(a[i]=2\)). Nếu dãy số của ai được sắp xếp lại sao cho nhiều \(pn[i]\) là số nguyên tố nhất thì người đó giỏi nhất.

Trong đó \(pn[i]\) là tổng \(i\) số đầu tiên của dãy số trên sau khi sắp xếp. Ngay khi vừa sinh ra Hạo được chính phủ cấp cho mình một dãy số tương tự như trên. Bố mẹ Hạo muốn nhờ bạn giúp sắp xếp lại để Hạo giỏi nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên dương \(𝑁\) là số lượng số chính phủ cấp cho Hạo.
• Dòng thứ hai chứa \(𝑁\) số nguyên dương mà chính phủ cấp cho Hạo.

Output

• Một số nguyên duy nhất là số lượng giá trị \(pn[i]\) là số nguyên tố.

Ràng buộc:

• Có \(30%\) số lượng test ứng với \(30%\) số điểm thỏa mãn điều kiện: \(𝑁 \le 10\).
• Có \(70%\) số lượng test còn lại ứng với \(70%\) số điểm thỏa mãn điều kiện: \(𝑁 \le 10^5\)

Sample input

4
2 2 1 1

Sample out

3

Giải thích ví dụ:

• Sắp xếp \({2, 2, 1, 1}\) thành \({2, 1, 2, 1}\). Khi đó \(pn\) = \({2, 3, 5, 6}\). Xuất hiện \(3\) số nguyên tố trong \(pn\).