Cho số nguyên dương ~n~ và dãy số nguyên dương ~a_1,a_2,…,a_n~ đôi một khác nhau.

Yêu cầu: Hãy cho biết có bao nhiêu hoán vị của dãy số sao cho tổng của ba số liên tiếp trong hoán vị là một số nguyên tố?

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên dương ~n~ ~(3≤n≤15)~;
• Dòng thứ hai ghi lần lượt các số ~a_1,a_2,…,a_n~ ~(1≤a_i≤200;1≤i≤n)~.

**Kết quả: **

• Một số nguyên cho biết kết quả bài toán.

Ví dụ:

Input

4
3 5 2 6 

Output

4 

Giải thích ví dụ: các hoán vị thỏa mãn yêu cầu bài toán là:

~3, 2, 6, 5~;

~3, 6, 2, 5~;

~5, 2, 6, 3~;

~5, 6, 2, 3~

Ràng buộc:

• Có 70% số test tương ứng với 70% số điểm có ~≤10~
• Có 30% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm.