N,*P=eval *$<
q=[[1,0]]
q.map{|j,v|j>N||j>0&&P[j]||=q<<[j+b=("%b"%j).count(?1),v+=1]<<[j-b,v]&&v}
p P[N]||-1