• 제곱수의 합 (More Huge)의 (많이) 쉬운 버전. Four Squares과는 거의 동일한 문제이다
• 풀이는 제곱수의 합을 참고. Four Squares와 동일한 코드를 사용했다

"""Solution code for "BOJ 1699. 제곱수의 합".

- Problem link: https://www.acmicpc.net/problem/1699
- Solution link: http://www.teferi.net/ps/problems/boj/1699

Tags: [Math]
"""

import math


def main():
    N = int(input())
    squares = {i * i for i in range(1, math.isqrt(N) + 1)}
    if N in squares:
        print(1)
    elif any(N - x in squares for x in squares):
        print(2)
    else:
        while N % 4 == 0:
            N //= 4
        print(4 if N % 8 == 7 else 3)


if __name__ == '__main__':
    main()