Closing the Windows

Count how many of the N windows end up open after each person toggles the windows whose numbers are multiples of their index.

Medium4MathNumber theoryNo attempts yetTime limit1sMemory limit64 MB

Problem

A lab room has NN windows and NN people. The windows are numbered 11 through NN, and every window starts closed.

Person ii visits every window whose number is a multiple of ii. At each of those windows, the person closes it if it is open and opens it if it is closed. Person 11 acts first, then person 22, and so on through person NN. Count how many windows are open at the end.

For N=3N = 3 the process runs like this.

  1. Person 11 opens windows 1,2,31, 2, 3, the multiples of 11. The state is (open, open, open).
  2. Person 22 closes window 22, the multiple of 22. The state is (open, closed, open).
  3. Person 33 closes window 33, the multiple of 33. The state is (open, closed, closed).

Exactly 11 window is open at the end.

Input

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

Output

Print how many windows are open at the end.