import sys
sys.setrecursionlimit(10000)
n=int(input())
data={}
for i in range(1,n+1):
    data[i]=-1
data[1]=1

def check(index,count=2):
    global data
    move=sum(map(int,bin(index)[2:]))
    if index-move>0:
        if data[index-move]==-1:
            data[index-move]=count
            check(index-move,count+1)
    if index+move<=n:
        if data[index+move]==-1:
            data[index+move]=count
            check(index+move,count+1)
check(1)
print(data[n])