N=gets.to_i
a=[b=c=1]
a<<b while N>=b+=c+=1
if a[-1]==N
  p 1
  exit
end
a.repeated_combination(2).each{|d,e|
  if d+e==N
    p 2
    exit
  end
}
p 3