Blue Flag, White Flag

Each of N players flips every flag whose number is a multiple of their index; count how many flags end white side up.

Easy3MathNumber theoryImplementationBrute forceInterviewNo attempts yetTime limit1sMemory limit128 MB

Problem

A flag flipping game is under way at the sports day held by the college student council. The software department and the ICT convergence department take turns playing. The rules are simple. The department whose turn it is sends out NN players. On the table in front of them sit NN flags numbered 11 to NN, each lying blue side up and white side down.

The first player turns over every flag whose number is a multiple of 11. The second player turns over every flag whose number is a multiple of 22. In the same way, the ii-th player turns over every flag whose number is a multiple of ii, and the game ends once the NN-th player is done.

With NN players and NN flags, count the flags lying white side up after the NN-th player has finished.

Input

The first line contains NN, the number of players and also the number of flags. (1N21000000001 \le N \le 2100000000)

Output

Print on the first line the number of flags lying white side up after the NN-th player has finished.

Hint

Take N=3N = 3. Flags 11, 22, 33 are on the table and three players take part. The first player turns over every flag whose number is a multiple of 11, so all three flags, blue side up at the start, end up white side up. The second player turns over flag 22, the only multiple of 22, leaving the flags white, blue, white. The last player turns over flag 33, the only multiple of 33, leaving them white, blue, blue. One flag lies white side up.