import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N = int(input())
Frm, To = [], []
for i in range(1, N + 1):
    b = bin(i).count('1')
    if i - b >= 1:
        Frm.append(i)
        To.append(i - b)
    if i + b <= N:
        Frm.append(i)
        To.append(i + b)

matr = csr_matrix((np.ones_like(Frm, dtype=int), (Frm, To)), shape=(N + 1, N + 1))
way = dijkstra(matr, indices=1).astype(int)
print(ans if (ans := way[N] + 1) > 0 else -1)