from collections import deque n = int(input()) q = deque() dp = [10**12]*(n+1) dp[1] = 1 q.append(1) def pc(x): r = 0 for i in range(6): r += (x>>i)%2 return r while q: i = q.popleft() p = pc(i) if 0 < i+p <= n and dp[i+p] > dp[i]+1: dp[i+p] = dp[i]+1 q.append(i+p) if 0 < i-p <= n and dp[i-p] > dp[i]+1: dp[i-p] = dp[i]+1 q.append(i-p) if dp[n] == 10**12: print(-1) else: print(dp[n])