836. Number of Actions Required to Defeat the Villain

0

Easy

Junoon desires to obtain the Brahmastra, but Shiva opposes Junoon's goal. Junoon possesses an initial power P. Shiva has the ability to perform the following actions:
  • If Junoon's current power is even, it can be halved by dividing it by 2.
  • If Junoon's current power is odd, it can be reduced by subtracting one from it.
Shiva seeks assistance in determining the number of actions required to reduce Junoon's power to zero. Can you help Shiva?

Input Format

Input a single line containing an integer P, which represents Junoon's initial power.

Output Format

Output the total number of actions required by Shiva to reduce Junoon's power to zero.

Example

Input

14

Output

6

Constraints

1<=P<=10^18
Loading...

View Submissions

Console