import times, strutils, sequtils, math, algorithm, tables, sets, lists, intsets
import critbits, future, strformat, deques
template `max=`(x,y) = x = max(x,y)
template `min=`(x,y) = x = min(x,y)
template `mod=`(x,y) = x = x mod y
template scan2 = (scan(), scan())
template scan3 = (scan(), scan())
let read* = iterator: string {.closure.} =
    while true: (for s in stdin.readLine.split: yield s)
proc scan(): int = read().parseInt
proc scanf(): float = read().parseFloat
proc toInt(c:char): int =
    return int(c) - int('0')



proc solve():int=
  var
    n = scan()
    yen = newseq[int]()
    isSankaku = newseqwith(n+1,false)
  for k in 1..<int.high:
    if (k*(k+1)).div(2) <= n:
      yen.add((k*(k+1)).div(2))
      isSankaku[(k*(k+1)).div(2)] = true
    else:
      break
  if isSankaku[n]:
    return 1
  else:
    for coin in yen:
      if isSankaku[coin] and isSankaku[n-coin]:
        return 2
    return 3


  
echo solve()