Sum of Squares

Some natural numbers, such as ~17~, can be expressed as the sum of two squares of natural numbers: ~17 = 1^2 + 4^2~. Others, like ~42~, cannot be written in this form. Some natural numbers, like ~25~, can be expressed in this form in more than one way: ~25 = 0^2 + 5^2 = 3^2 + 4^2~.

Problem:

Develop a program in one of the IOI languages that reads some natural numbers and finds in how many different ways each of them can be written as the sum of two squares of natural numbers.

Input Files:

The input files named twosqr.in are text files with the following structure: The first line contains exactly one natural number T ~(1 \le T \le 1.000)~, the number of numbers that will follow. ~T~ lines follow, each containing exactly one natural number Ν~\mathbf{i}~ ~(0 \le N_i \le 1.000.000.000)~.

Output Files:

The output files named twosqr.out are text files with the following structure: They have exactly ~T~ lines, each containing an integer: the number of ways in which the corresponding input number ~N_i~ can be written as the sum of two squares of natural numbers.

Example of Input - Output Files:

STDIN (twosqr.in)

6
17
42
65
0
1025
203125

STDOUT (twosqr)

1
0
2
1
3
7

Maximum Execution Time: 1 sec