## 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