let i = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n')[0]
let a = []
for (let c = 1; c <= i; c++) {
  let n = 0
  c.toString(2).split('').forEach((e) => e === '1' ? n++ : n)
  a.push(n)
}
const f = (x, y, a, d) => {
  if (x == a.length - 1) return d
  if (x < 0 || x >= a.length) return -1
  if (y.indexOf(x) > -1) return -1
  let m = y.concat()
  m.push(x)
  let r1 = f(x - a[x], m, a, d+1)
  let r2 = f(x + a[x], m, a, d+1)
  if (r1 == -1 && r2 == -1) return -1
  if (r1 == -1) return r2
  if (r2 == -1) return r1
  return r1 > r2 ? r2 : r1
}
console.log(f(0, [], a, 1))