import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); if (N == 1) { System.out.println(1); return; } //各マスの移動距離を事前に計算 O(N) int[] map = new int[N+1]; for (int i = 1; i <= N; i++) { map[i] = Integer.bitCount(i); } //戻らずに行ける範囲を最初に計算 int[] dp = new int[N+1]; Arrays.fill(dp, Integer.MAX_VALUE-500); dp[1] = map[1]; boolean changed = true; while(changed) { changed = false; for (int i = 1; i <=N; i++) { if (i-map[i] > 0 && dp[i-map[i]] > dp[i]+1) { dp[i-map[i]] = dp[i]+1; changed = true; } if (i+map[i] <= N && dp[i+map[i]] > dp[i]+1) { dp[i+map[i]] = dp[i]+1; changed = true; } } } System.out.println(dp[N] == Integer.MAX_VALUE-500 ? -1 : dp[N]); } }