import java.util.*; public class No3 { public static void main (String[] args) { Scanner scan = new Scanner(System.in); int N = scan.nextInt(); //tmp:今いるマスの目のコピー //mov:動けるマス数 loc:今いるマス目 //flag:一度も動けない事があるかを監視 int tmp; int ans = -1; int mov; boolean flag; //すでに行ったことのあるマスを記憶 boolean[] went = new boolean[N+1]; //次に行くマスを記憶 boolean[][] next = new boolean[N+1][N+1]; for (int i = 0; i < N+1; i++) { went[i] = false; for (int j = 0; j < N+1; j++) { next[i][j] = false; } } next[1][1] = true; for (int i = 1; i < N+1; i++) { flag = false; for (int j = 1; j < N+1; j++) { if (next[i][j]) { flag = true; if (j == N) { ans = i; break; } mov = 0; tmp = j; //2進数のときbitが1の数を数える while (tmp != 0) { mov += tmp & 1; tmp = tmp >> 1; } went[j] = true; //次に行けるマスを追加 if (j + mov < N + 1 && !went[j + mov]) next[i + 1][j + mov] = true; else if (j - mov > 0 && !went[j - mov]) next[i + 1][j - mov] = true; } } if (!flag) break; } System.out.print(ans); } }