Sum of Squares (More Huge)

In 1770, Lagrange proved that every natural number can be expressed as the 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 expressed as $4^2 + 3^2 + 1^2$. Historically, the problem commonly given to mental calculation experts was to represent a natural number as a sum of four or fewer squares. In the early 1900s, one mental calculator was reported to have taken 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 computer program that expresses $n$ as the sum of the fewest possible squares.

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

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