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
#!/usr/bin/python

num = int(raw_input())
div = 8192
count = 0
while div > 0:
	if num >= div:
		count = count + 1
		num = num - div
	div = div / 2
print count