N=gets.to_i
A=(0..N).map{|i|i.to_s(2).count ?1}
h=->n,r{
  if n < 4
    ([*1..n]+r|[]).size
  else
    m=([*n-n.bit_length..N]-r).select{|i|i+A[i]==n||i-A[i]==n}.min_by{|i|h[i,r+[i]]}
    break 1e5if !m
    h[m,r<<m]
  end
}
p h[N,[N]]