# Problem H

Tightly Packed

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.

Sample Input 1 | Sample Output 1 |
---|---|

47 |
1 |

Sample Input 2 | Sample Output 2 |
---|---|

523 |
2 |

Sample Input 3 | Sample Output 3 |
---|---|

10000000000001 |
6 |