Sum of Squares

A positive integer N can be represented as a sum of square numbers that are no greater than N. For example, 11 can be written as 3^2 + 1^2 + 1^2 using three terms, and it can also be written as 2^2 + 2^2 + 1^2 + 1^2 + 1^2 using five terms.

Among all possible representations, find the minimum number of square-number terms needed.

The first line contains a positive integer N. (1 <= N <= 100,000)

Print the minimum number of square-number terms needed to represent N as a sum of squares.