This is the algorithmic version of a game that kids play in our part of the country. You will be provided with a few sticks. The length of the sticks will be in the order of powers of 2. (1,2,4,8,16,32....). You will also be given another test stick of any length. The task is to write a program that finds the minimum number of sticks required to make the required test stick.

Input
A positive integer in the range 1 to 10000

Output
A positive integer denoting the minimum number of sticks

Example

Input:
5

Output:
2

见题面

见题面