U503552 村庄的友谊

在一个遥远的村庄里，村民们的契合度是一个重要的特征。每个村民都有一个契合度，契合度的值为 $1$ 到 $n$ 之间的任意整数。村民们之间的友谊是基于他们的契合度：只有当两个村民的契合度相乘的结果**是质数**时，他们才能成为朋友，否则他们就是陌生人，即使他们可能有相同的朋友。 现在，村庄的长老希望了解村庄中有多少对**不同**的**陌生人**。请你帮助长老计算出来。

- 第一行输入一个整数 $n\ (1 ≤ n ≤ 5*10^5)$，表示村民的数量。 - 第二行输入 $n$ 个整数，表示每个村民的契合度，契合度的值在 $1$ 到 $5*10^5$ 之间。

输出一个整数，表示村庄中有多少对**不同**的**陌生人**。

## 数据范围 对于 $20\%$ 的数据，$1