# coding: utf-8 N = int(input()) saitan = [-1] * N # 各節点における最短移動数、-1は移動不可 tansaku_zumi = [] # 探索済みの節点を格納するリスト tugi = [] # 次に調べる節点のリスト #初期化 saitan[0] = 1 # 節点1の最短移動数は1 tansaku_zumi.append(1) # 1を探索済にする tugi.append(1) while tugi and not N in tansaku_zumi: # 次に調べる節点が存在、かつ節点Nが探索済みで無いとき継続 tugi_t = [] for i in tugi: step = bin(i).count("1") # iを2進数にしたときの1のビット数 if (i - step) >= 1 and not((i - step) in tansaku_zumi): # i - step が境界を超えず、かつ未探索のとき saitan[i - step - 1] = saitan[i - 1] + 1 tansaku_zumi.append(i - step) tugi_t.append(i - step) if (i + step) <= N and not((i + step) in tansaku_zumi): # i - step が境界を超えず、かつ未探索のとき saitan[i + step - 1] = saitan[i - 1] + 1 tansaku_zumi.append(i + step) tugi_t.append(i + step) tugi = tugi_t[:] #print(saitan) #print(tugi) #print(tansaku_zumi) #print(saitan) print(saitan[-1]) # 節点Nの最短移動数を出力