Đếm cặp có số nguyên tố

Cho dãy \(A_1, A_2, \dots, A_N\) gồm các số nguyên dương. Hãy đếm số cặp vị trí \((i, j)\) với \(1 \le i < j \le N\) sao cho ít nhất một trong hai giá trị \(A_i\), \(A_j\) là số nguyên tố.

Các cặp được xác định theo vị trí trong dãy (hai phần tử bằng giá trị nhau nhưng ở hai vị trí khác nhau vẫn là hai cặp khác nhau), và cặp \((i, j)\) với \((j, i)\) chỉ tính một lần.

Input

• Dòng 1: số nguyên \(N\).
• Dòng 2: \(N\) số nguyên dương \(A_1, \dots, A_N\).

Output

• Một số nguyên: số cặp thoả mãn.

Constraints

• \(2 \le N \le 10^5\)
• \(1 \le A_i < 10^9\)

Sample Input

5
1 4 6 2 9

Sample Output

4

Explanation

Chỉ có \(A_4 = 2\) là số nguyên tố. Các cặp thoả mãn đều chứa vị trí \(4\): \((1,4), (2,4), (3,4), (4,5)\).