Sum of Squares

Interview

Time limit2sMemory limit128 MB

Summary

Given N up to 100,000, find the minimum number of perfect squares that sum to N.

Level: Medium4 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

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.

Input

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

Output

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

Examples5

Example 1
Input
```
7
```
Expected output
```
4
```
Example 2
Input
```
1
```
Expected output
```
1
```
Example 3
Input
```
4
```
Expected output
```
1
```
Example 4
Input
```
11
```
Expected output
```
3
```
Example 5
Input
```
13
```
Expected output
```
2
```