The long night P12494

The TV series took its downturn in an unrealistic battle between the army of the undead (also called white walkers) and the army of living humans. George has decided to fix it, by writing the story in the best possible way: using math.

Suppose that the army of the undead has w white walkers and the army of the living has h ‍humans. Repeatedly, pick a creature at random and let it kill one of its enemies. Therefore, a walker is killed with probability h/(h+w), and a human is killed otherwise. If a walker dies, nothing else happens. If a human dies, however, it turns into a walker!

The battle ends when one of the armies loses all its warriors. Note that, for large numbers, when h = w humans clearly have a very small chance of victory, whereas when h ≫ w their chances are very high.

Help George figure out who should win the battle and how to keep it optimally interesting. In particular, given the number of walkers w, can you determine the minimum number of humans h so that the army of the living has at least a 50% chance of victory?

Input

Input consists of several cases, each with a w between 1 and 10¹⁵.

Output

For every w, print the minimum number of humans h so that an army of h humans will have at least a 1/2 probability of winning a battle against w white walkers. You are allowed to miss your answer by 1 unit. A special corrector will handle it.