def go(n):
    ary = list(format(n,'b'))
    g = sum([int(a) for a in ary])
    return g


def sugoroku_map(val,debug=False):
    dic = {a:[a+go(a), a-go(a)] for a in range(1,val)}
    if debug:
        print(dic)
    return dic

def update_tree(val,dic, ary=[[1]]):
    reary = []
    flag = False
    for a in ary:
        b =list(a) 
        last = a[-1]
        if last in dic:
            el = dic[last]
            if val in el:
                flag = True
            if last == val:
                reary.append(a)
            else:
                # foward
                if (el[0] <= val) and (el[0] > 1) and (el[0] not in a):
                    a.append(el[0])
                    reary.append(a)
                # back
                if (el[1] <= val) and (el[1] > 1) and (el[1] not in b):
                    b.append(el[1])
                    reary.append(b)
        else:
            reary.append(a)
    return flag, reary


def main(debug=False):
    val = input()
    val = int(val)
    # make tree
    tree = [[1]]
    sugo_map=sugoroku_map(val, debug)
    for i in range(1,val):
        flag, tree = update_tree(val,sugo_map,tree)
        if debug:
            print(tree)
        if flag:
            print(len(tree[0]))
            return
    # tree length 
    length = [len(el) for el in tree if el[-1] == val]
    if len(length) > 0:
        print(min(length))
    else:
        print(-1)

main(debug=False)