====== 제곱수의 합 ======

===== 풀이 =====
  * [[ps:problems:boj:17633]]의 (많이) 쉬운 버전. [[ps:problems:boj:17626]]과는 거의 동일한 문제이다
  * 풀이는 [[ps:제곱수의 합]]을 참고. [[ps:problems:boj:17626]]와 동일한 코드를 사용했다

===== 코드 =====
<dkpr py>
"""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()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_2}}