Challenge 11: Least Perfect Squares

Caleb is now in Upper El and is currently tackling multiplication and division. He recently discovered squared numbers and was wondering the following:

Given a positive integer n, what is the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, for the number 12, he knows he can use three 4s (which is a perfect square) to add up to 12.

Likewise, for the number 13, he has determined that he can use 4 and 9 to sum up to 13.

Caleb would like for you to write a program than determines what is the least number of perfect squares required to sum up to any arbitrary positive integer n.

Input

Each line of input will be a positive integer n. You are to find the least number of perfect square numbers that sum up to n.

Example Input

12
13

Output

For each input number n, print out the least number of perfect square numbers that sum up to n.

Example Output

3
2

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa20-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge11               # Create and checkout challenge11 branch

$ $EDITOR challenge11/program.cpp           # Edit your code

$ git add challenge11/program.cpp           # Stage your changes
$ git commit -m "challenge11: done"         # Commit your changes

$ git push -u origin challenge11            # Send changes to GitHub

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge11 assignment ...
Submitting challenge11 code ...
  Result Success
   Score 6.00
    Time 2.22

$ curl -F source=@challenge11/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa20/challenge11
{"result": "Success", "score": 6, "time": 2.368675708770752}