Psychological comfort P97833


Statement
 

pdf   zip

thehtml

Professor Oak is getting old, as he can notice at the gym. Now, when he is on the running machine, he needs some psychological tricks to go on. For instance, supose that he decides to run for m = 20 minutes. Then, when he has been running for 2 minutes, he thinks “already 1/10 done”. Similarly, at the minute 17, he thinks “only 3/20 left”. Note that Prof. ‍Oak solely likes fractions whose only prime factors (when simplified) are 2, 3 and 5. So, for m = 20, the minute 7 is not psychologically comforting, because both 7/20 and 13/20 have factors other than 2, 3 and 5.

Given m, how many psychologically comforting minutes will Prof. Oak enjoy?

Input

Input consists of several cases, each with an m between 1 and 1015.

Output

For every m, print the number of psychologically comforting minutes between 1 and m−1.

Public test cases
  • Input

    1
    10
    20
    66
    81
    1000000007
    1000000000000000
    

    Output

    0
    9
    17
    5
    50
    0
    12909
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++