Cho dãy ~n~ số nguyên dương ~a_1,a_2,\ldots,a_n~. Cặp chỉ số ~(i,j)~ với ~1 \le i < j \le n~ được gọi là cặp số nguyên tố nếu ~a_i+a_j~ là số nguyên tố.

Yêu cầu

Đếm số lượng cặp số nguyên tố trong dãy.

Input

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

Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(1 \le a_i \le 10^6)~.

Output

In ra một số nguyên là số lượng cặp số nguyên tố.

Subtask

• Có 60% số test có ~3 \le n \le 10^2~.
• Có 40% số test còn lại không có ràng buộc bổ sung.

Ví dụ

4
1 3 6 2

3