题目描述

Note: the description is really long. For better understanding, important conceptions are in bold style.

Fourier has started a project with his friends, aiming to research into the ultimate theory for the whole universe.

Georg Cantor, the trailblazer in set theory, uses 'Marvelous Cantor Set(MCS)' to describe the universe. In plain language, the MCS contains all the integers from $1$ to $n$.

René Descartes, who has invented a lot of important operators, uses 'Profound Descartes Operator(PCO)' to describe how the elements in MCS interact with each other. In plain language, when PCO is exerted on exactly two elements in MCS, the product of the two elements shall be returned. Moreover, the PCO is only defined between two numbers with product no more than $n$.

Leonhard Euler, the master of number theory, has discovered the fundamental elements in MCS. He names them 'Fabulous Euler Number(FEN)'. In his research, he finds that all the PCOs of two different prime numbers , are FEN.

George Boole, the pioneer in boolean logistic, has perfected the definition of FEN. He uses 'Excellent Boole Law(EBL)' for it, which contains two descriptions:

  • the PCO of two FENs are FEN , as long as the PCO between them is defined. Note that the two FENs can be the same.

  • no other numbers than all the PCOs of two different prime numbers and the PCOs of two FENs , are FENs.

Through hundreds and thousands of great scientists' investigations, the algebra in MCS has finally be fulfilled. However, the law of converting of normal natural numbers to elements in MCS hasn't been found, and in long time periods, MCS algebra was not widely used.

Finally, Fourier, the genius transformation researcher, advanced 'Final Fourier Transformation(FFT)' for this problem. The theorem is an epochal discovery, although with a small flaw: FFT requires to count the number of FENs in MCS , however Fourier doesn't know how to do it!

Help Fourier with this problem! If you can solve it successfully, there may be a constant named after you!


输入格式

One line with a single number, $n (1\leq n\leq 10 ^ {11})$.


输出格式

One line with a single number, which is the number of FENs in MCS.


样例数据

输入

10

输出

2

备注

In this case, only $6$


操作

评测记录

优秀代码

信息

时间限制: 2s
内存限制: 128MB
评测模式: Normal

题解