三人组有多少种

题目描述

给定整数 n，统计满足 p≤q≤r、p、q、r 均为质数且 p+q+r=n 的三元组数量。允许重复使用同一个质数；交换顺序不产生新方案。

输入格式

一行输入整数 n，满足 6≤n≤5000。

输出格式

输出不同不递减质数三元组的数量。

样例

输入

6

输出

1