import java.io.*; import java.util.Arrays; import java.util.Deque; import java.util.ArrayDeque; class Main{ public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String line=""; int[] map=new int[10001]; Arrays.fill(map,-1); Deque que=new ArrayDeque(); map[1]=1; que.offerLast(1); if(que.peekFirst()!=null){ int n=que.pollFirst(); if(n+numOfOne(n)<=10000&&map[n+numOfOne(n)]==-1){ map[n+numOfOne(n)]=map[n]+1; que.offerLast(n+numOfOne(n)); } if(n-numOfOne(n)>1&&map[n-numOfOne(n)]==-1){ map[n-numOfOne(n)]=map[n]+1; que.offerLast(n-numOfOne(n)); } } while((line=br.readLine())!=null){ int t=Integer.parseInt(line); System.out.println(map[t]); } } private static int numOfOne(int n){ int count=0; String val2=Integer.toBinaryString(n); for(int i=0;i