Consider packing widgets for shipping where widgets cannot be stacked upon each other (2D packing). Each widget has a $1\times ~ l$ footprint and is $1$ unit high.

Boxes are available in any $W$ by $H$ by $1$ size such that $H/2 \leq W \leq 2H$, with $W$ and $H$ being integers. The company wants to minimize the amount of packing material that will be needed to fill empty squares in a box.

Given $N$, the number of widgets to be shipped, what is the smallest number of squares that will be left empty when those widgets are packed for shipping?

-----Input-----
Input consists of one line containing an integer $N$, the number of widgets to be packed, where $1 \leq N \leq 10^{16}$.

-----Output-----
Print a single line containing an integer denoting the minimum number of empty squares.

-----Examples-----
Sample Input 1:
47
Sample Output 1:
1

Sample Input 2:
523
Sample Output 2:
2

见题面

见题面