Jaiden has decided to leave the corporate world behind, and has just started his very own boutique high frequency trading company. Things have been running smoothly and profits are being turned, but unfortunately Jaiden's trading algorithm is leaking memory, meaning that it'll eventually crash if it isn't fixed. Lucky for him, if he has enough RAM, he doesn't actually need to debug and fix the memory leak as he can reboot outside of market hours.

After profiling the memory usage of the program, Jaiden finds that the number of bytes of memory leaked at ~t=x~ is equal to the number of ~1~'s in the binary representation of ~x~. For example, on a trading day that lasts 3 seconds, at ~t=1~, ~1~ byte of memory is leaked, at ~t=2~, ~1~ byte, and at ~t=3~, ~2~ bytes, for a total of ~4~ bytes of memory leaked.

Since RAM is rather expensive right now, Jaiden cannot buy any. As such, he'd like to find out how long his program will stay alive before having to restart given the RAM he currently has.

Input

The first and only line consists of a single integer ~n~ ~(1 \leq n \leq 10^{15})~, the number of bytes of RAM that Jaiden has.

Output

Output a single integer - the number of seconds that the program will stay alive. It is guaranteed that this answer will fit in a 64-bit integer.

Examples

Input

4

Output

3

At ~t=1~, ~1~ byte of memory is leaked.

At ~t=2~, another byte.

At ~t=3~, ~2~ more bytes.

All ~4~ bytes of RAM have been used, and as such the program will last ~3~ seconds.

Input 2

10

Output 2

6

At ~t=1~, ~1~ byte of memory is leaked.

At ~t=2~, ~1~ byte.

At ~t=3~, ~2~ bytes.

At ~t=4~, ~1~ byte.

At ~t=5~, ~2~ bytes.

At ~t=6~, ~2~ bytes.

At this point, a total of ~9~ bytes of memory have been leaked.

At ~t=7~, ~3~ bytes of memory would be leaked, which would push our total to ~12~ bytes of memory leaked, crashing the program. As such, the program will last ~6~ seconds.