#NC14615. Number

Number

题目描述

We define Shuaishuai-Number as a number which is the sum of a prime square(平方), prime cube(立方), and prime fourth power(四次方).

The first four Shuaishuai numbers are:

题目插图

How many Shuaishuai numbers in [1,n]? (1<=n<=50 000 000)

输入格式

The input will consist of a integer n.

输出格式

You should output how many Shuaishuai numbers in [1...n]

样例 1

28
1

样例说明

There is only one Shuaishuai number

来源

牛客原题