Lagrange's theorem on the sum of four squares#564

Lagrange's theorem on the sum of four squares

1 second
64 megabytes
Easy

The fact that any natural number can be represented as the sum of no more than four squares of natural numbers is known as Lagrange's theorem. The first proof of this theorem was given by Joseph Louis Lagrange in . You do not need to prove or disprove the theorem, since it is already established that such a representation exists for any natural number. Your task is to find the number of different representations of a given natural number as the sum of no more than four squares of other natural numbers. The order of terms does not matter; for example, representations such as 4^2 + 3^2 and 3^2 + 4^2 are considered the same.

For example, the number can be represented as the sum of squares in three ways: 1^2 + 2^2 + 2^2 + 4^2, 3^2 + 4^2, and 5^2.

Input

The first line contains the number of test cases (1 \leq T \leq 255). Each of the next lines contains a number for which you need to find the number of different representations as the sum of no more than squares of natural numbers. Each number does not exceed 2^{15}.

Output

For each test case, output the required number on a separate line.

Examples

Example 1

Loading
Loading