Trái Đất vào năm 14789654, số nguyên tố được ưu 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 ~M~ số nguyên dương, số thứ ~i~ nhận được giá trị ~a_i~ (hoặc ~a_i~ = 1 hoặc ~a_i~ = 2). Nếu dãy số của ~a_i~ đượ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 Agent P được chính phủ cấp cho mình một dãy số tương tự như trên. Bố mẹ Agent P muốn nhờ bạn giúp sắp xếp lại để Agent P giỏi nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên dương N là số lượng chính phủ cấp cho Agent P.
• Dòng thứ hai chứa N số nguyên dương mà chính phủ cấp cho Agent P

Output

• Một số nguyên duy nhất là số lượng giá trị ~pn_i~ là số nguyên tố

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~N < 10~.
• Subtask ~2~ (~70\%~ số điểm): ~N < 10^5~.

Ví dụ

Input

4
2 2 1 1 

Output

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~