제곱수의 합

자연수 N은 N보다 작거나 같은 제곱수 몇 개의 합으로 나타낼 수 있다. 예를 들어 11은 3^2 + 1^2 + 1^2처럼 세 항으로 표현할 수 있고, 2^2 + 2^2 + 1^2 + 1^2 + 1^2처럼 다섯 항으로도 표현할 수 있다.

가능한 모든 표현 중에서 사용하는 제곱수 항의 개수가 가장 적은 값을 구하시오.

첫째 줄에 자연수 N이 주어진다. (1 <= N <= 100,000)

N을 제곱수들의 합으로 나타낼 때 필요한 제곱수 항의 최소 개수를 출력한다.