U503552 村庄的友谊

题目描述

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

输入格式

输出格式

说明/提示

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