说明

时间限制：1 Sec 内存限制：256 MB 输入文件：psum.in 输出文件：psum.out

给定整数 $N$，请统计满足以下条件的三元组 $(a, b, c)$ 的数量：

1. $a、b、c$ 是不超过 $N$ 的互不相同的素数；
2. $2\le$ $a<b<c$ $\le N$；
3. $a + b + c$ 的结果为素数

输入格式

一个整数 $N$。

输出格式

一个整数，表示满足条件的三元组个数。

样例

样例 1

11

2

样例说明：

不超过 $11$ 的素数有 $2$、$3$、$5$、$7$、$11$，共 $5$ 个。从中选取满足 ( a < b < c ) 的三元组共有 $10$ 种组合，其中仅以下 $2$ 种满足 ( a + b + c ) 为素数：( 3 + 5 + 11 = 19 )、( 5 + 7 + 11 = 23 )。

样例 2

1000

241580

样例 3

10000

74588542

样例 4

100000

28694800655

数据范围

对于 8% 的数据，$N \le 100$。

对于 16% 的数据，$N \le 500$。

对于 28% 的数据，$N \le 1000$。

对于 40% 的数据，$N \le 5000$。

对于 100% 的数据， $ 5 \le N \le 100000 $。