import java.util.ArrayList; import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); boolean[] check = new boolean[N + 1]; System.out.println(bfs(N, check)); } private static int bfs(int n, boolean[] check) { LinkedList queue = new LinkedList(); LinkedList nextQueue = new LinkedList(); queue.add(1); for (int turn = 1; queue.size() > 0; turn++) { while (queue.size() > 0) { int v = queue.pop(); if (v == n) { return turn; } check[v] = true; int bitCount = getBitCount(v); int a = v - bitCount; int b = v + bitCount; if (a > 0) { if (!check[a]) { nextQueue.push(a); } } if (b <= n) { if (!check[b]) { nextQueue.push(b); } } } queue.addAll(nextQueue); nextQueue.clear(); } return -1; } static int getBitCount(int n) { int count; for (count = 0; n > 0; count++) { n = n & (n - 1); } return count; } }