LUDIC2  Ludic Numbers (hard)
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.
hide comments
Oleg:
20240130 05:44:31
Amazing problem! 

kamol_paul:
20210421 21:41:19
Is there any editorial of this problem? 

dacin21:
20180511 13:11:51
@Min_25


Min_25:
20180511 12:20:46
@dacin21:


dacin21:
20180511 10:42:23
@Min_25 Thanks for posting this problem. I liked the idea I used to optimize from LUDIC1 to LUDIC2. How fast does your solution run? My solution builds on top of my slow LUDIC1 solution, so it's quite slow. 
Added by:  Min_25 
Date:  20180412 
Time limit:  25s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 