<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css" integrity="sha384-wITovz90syo1dJWVh32uuETPVEtGigN07tkttEqPv+uR2SE/mbQcG7ATL28aI9H0" crossorigin="anonymous">

Find the number of Ludic numbers less than or equal to $N$.

Input

The first line contains an integer $N$ ($1 \le N \le 10^{11}$).

Output

Output the number of Ludic numbers less than or equal to $N$.

Example

Input

100000000000

Output

3603128157

Note

• See LUDIC1 for an easier version.
• Other references for the Ludic numbers: Ludic numbers or A003309.