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