Closing the Windows

Time limit1sMemory limit64 MB

Summary

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

Level: Medium4 of 10
Topics: Math, Number theory
Solved: No attempts yet

Problem

A lab room has $N$ windows and $N$ people. The windows are numbered $1$ through $N$ , and every window starts closed.

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

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

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

Exactly $1$ window is open at the end.

Input

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

Output

Print how many windows are open at the end.

Examples2

Example 1
Input
```
3
```
Expected output
```
1
```
Example 2
Input
```
24
```
Expected output
```
4
```