def solve(n)
  k = 1
  t = Array(Int32).new
  e = Set(Int32).new
  while true
    m = k * (k + 1) / 2
    return 1 if m == n
    break if m > n
    t << m
    e.add(m)
    k += 1
  end
  t.each do |m|
    return 2 if e === (n - m)
  end
  3
end

n = gets.not_nil!.to_i
p solve n