n = gets.not_nil!.to_i
k = ((Math.sqrt(1 + 8 * n) - 1) / 2).to_i
tris = [] of Int32
istri = {0 => false}

1.upto(k) do |i|
  tri = i * (i + 1) / 2
  tris << tri
  istri[tri] = true
end

if tris.includes? n
  p 1
else
  ok = false
  tris.each do |a|
    break if ok
    ok = ok || (istri[n-a]? && istri[a]?)
  end
  p ok ? 2 : 3
end