N = int(input()) array = [] for i in range(1, N): array.append(str(bin(i))[2:].count("1")) count = 0 queue = [0] while(True): count += 1 n = array[queue[0]] # 現在の位置のビット数をnに代入 array[queue[0]] = 0 # 訪問履歴を0で表現する。すでに訪問した位置のビット数は0 a = queue[0] + n # 現在の位置+現在の位置のビット数をaに代入 b = queue[0] - n # 現在の位置-現在の位置のビット数をbに代入 queue.pop(0) if(a == N - 1): break if(0 < a < N - 1 and array[a] != 0): queue.append(a) if(0 < b < N - 1 and array[b] != 0): queue.append(b) if(len(queue) == 0): count = -1 break print(count)