Four Squares

Interview

Time limit0.5sMemory limit512 MB

Summary

Given n up to 50,000, print the minimum number of perfect squares whose sum equals n.

Level: Medium5 of 10
Topics: Dynamic programming, Math, Brute force, Number theory
Solved: No attempts yet

Problem

In 1770 Lagrange proved that every natural number can be written as a sum of four or fewer squares. Some natural numbers have more than one such representation. For example, 26 is the sum of $5^2$ and $1^2$ ; it can also be written as $4^2 + 3^2 + 1^2$ . Historically, the problem commonly given to mental-calculation experts was to express a natural number as a sum of four or fewer squares. In the early 1900s, one mental calculator was reported to take 8 seconds to find the solution $15663 = 125^2 + 6^2 + 1^2 + 1^2$ . A harder problem took 56 seconds: $11339 = 105^2 + 15^2 + 8^2 + 5^2$ .

Given a natural number $n$ , write a program that expresses $n$ as a sum of squares using the minimum number of squares.

Input

Input comes from standard input. The input consists of one line containing the natural number $n$ , where $1 \le n \le 50{,}000$ .

Output

Output goes to standard output. Print, on one line, the minimum number of squares whose sum equals $n$ .

Examples4

Example 1
Input
```
25
```
Expected output
```
1
```
Example 2
Input
```
26
```
Expected output
```
2
```
Example 3
Input
```
11339
```
Expected output
```
3
```
Example 4
Input
```
34567
```
Expected output
```
4
```