Lagrange's Four-Square Theorem

Time limit2sMemory limit128 MB

Summary

For each input number, count the unordered ways to express it as a sum of one to four positive perfect squares.

Level: Medium4 of 10
Topics: Brute force, Math, Combinatorics
Solved: No attempts yet

Problem

Every positive integer can be written as a sum of at most four squares. This fact is known as Lagrange's four-square theorem, proved by Joseph-Louis Lagrange in 1770.

We do not need to prove the theorem or discover a new one. Instead, given $n$ , we want to count the number of ways to write $n$ as a sum of at most four positive squares. Two representations that differ only in the order of the squares are considered the same, so $3^2 + 4^2$ and $4^2 + 3^2$ count as one.

For example, when $n = 25$ there are three such representations: $1^2 + 2^2 + 2^2 + 4^2$ , $3^2 + 4^2$ , and $5^2$ .

Input

The input contains at most $255$ lines. Each line holds a single positive integer smaller than $2^{15}$ . The last line contains a single $0$ , which is not part of the data.

Output

For each input value $n$ , output the number of ways to write $n$ as a sum of at most four positive squares (order does not matter), one per line.

Examples3

Example 1
Input
```
1
25
2003
211
20007
0
```
Expected output
```
1
3
48
7
738
```
Example 2
Input
```
4
7
0
```
Expected output
```
2
1
```
Example 3
Input
```
50
100
0
```
Expected output
```
5
7
```