Anniversary#1906
In the year , when the Earth's population reached 10^{18}, the people decided to celebrate this event. diminutive bulbs (the linear size of each bulb was less than millimeters) were placed on a huge area specially allotted for the celebration. The bulbs were numbered with consecutive integers from to in some order.
In the beginning, all the bulbs were off. Afterwards, exactly 10^{18} steps were performed—one for each citizen of Earth. At the -th step, the states of all bulbs with numbers such that divides were toggled simultaneously. Toggling means that if a bulb is off, it is turned on, and if it is on, it is turned off. The interval between consecutive steps was picosecond, so the whole celebration took about a week and a half.
To an external observer, this looked like pointless, chaotic flickering, yet everyone was amazed by the sheer scale of the event!
Eventually, it ended. There was nothing more to see; and upon further reflection—there never really was much to see at all.
After step 10^{18}, some bulbs remain on. While the people recover from shock and ponder the need for such a celebration and how to pay its astronomical costs, you are asked to count how many bulbs are still on and consuming precious electricity.
The only line of input contains the integer (1 \le N \le 2^{63} - 1).
Print a single integer — the number of bulbs which are still on after step 10^{18}.
Example 1