N=int(input()) #Nのビット数 n_bit=0 tmp=N while(tmp!=0): n_bit+=1 tmp=int(tmp/2) # print(n_bit) #'1'をカウント one_num_list=[0 for i in range(N+1)] for i in range(N+1): mask=0b1 one_sum=0 for l in range(n_bit): if i&mask!=0: one_sum+=1 mask=mask<<1 one_num_list[i]=one_sum #kに到達できる最小の移動数を順に調べていく(ただし-1のとき移動できないとする) move_num=[-1 for i in range(N+1)] #境界条件 move_num[0]=0 move_num[1]=1 #幅優先探索 queue=[] queue.append(1) ans=-1 while(1): if len(queue)==0: ans=-1 break # print(queue) k=queue.pop(0) one_num=one_num_list[k] if k+one_num==N: ans=move_num[k]+1 break #前の更新 if move_num[k-one_num]==-1 or move_num[k-one_num]>move_num[k]+1: move_num[k-one_num]=move_num[k]+1 queue.append(k-one_num) #後ろの更新 if k+one_num>N: continue if move_num[k+one_num]>move_num[k]+1 or move_num[k+one_num]==-1: move_num[k+one_num]=move_num[k]+1 queue.append(k+one_num) print(ans)