LUDIC2 - Ludic Numbers (hard)

no tags 

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



Added by:Min_25
Date:2018-04-12
Time limit:25s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All