import sys
input = sys.stdin.readline

N=int(input())

A=[k*(k+1)//2 for k in range(1,10**5)]

while A[-1]>10**7:
    A.pop()

DP=[1<<60]*(10**7+1)

for a in A:
    DP[a]=1

for a in A:
    for b in A:
        if a+b>10**7:
            break
        DP[a+b]=min(DP[a+b],2)

print(min(DP[N],3))