U503552 村庄的友谊

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

无

无

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