407556: GYM102829 C Kevin's Meme Reacts

Kevin loves his Pokemon memes and he thinks he has come up with an especially good one. He posts it into his Pokemon Showdown discord server and adds a single eye emoji react to hopefully start the chain of reacts.

Due to the high volume of traffic in the server, the reacts to his posts only update at the end of the day and he finds that every night, the number of reacts on his post doubles. He can also add a react to his post every morning and it will update immediately since it is his own post. Kevin wants exactly $$$n$$$ reacts on his post and being a lazy competitive programmer, he wants to react to his own post as few times as possible and still get the exact number of $$$n$$$ reacts.

Help Kevin figure out the minimum number of times he must react to his own post (including the first time he reacts to his post when he posted the meme) in order to have exactly $$$n$$$ reacts.

There is only one line of input that contains a single integer $$$n$$$ where $$$1 \leq n \leq 10^{9}$$$.

Output a single integer, the minimum number of times Kevin must react to his own post (including the first time he reacts when he posts the meme).

5

2

8

1

In the first test case, on the first day it starts with $$$1$$$ react, it will have $$$2$$$ by the start of the second day, and $$$4$$$ by start of the third day at which point he can add one more react to get exactly $$$5$$$. Thus, he has reacted to his own post exactly twice.

In the second test case, Kevin only needs to react once at the start, and then it doubles every day to reach $$$8$$$ by the start of the fourth day without Kevin needing to react again so he reacted exactly once.