1484 -- Equation
Time Limit :2000 MS Memory Limit :65536 KB
Accepts : 56 Submits : 283
User Accepts : 51 User Submits : 60
<Submit>   <Statistics>   <Discuss>

Description

Given r(1 ≤ r ≤ 3000000), find the number of solutions of the equation x2 + y2 + z2 = r where x, y and z are integers and in the range: [0, 1000].

Input

The first line of the input is a single integer n representing the number of test cases. Then n lines follows, In each line there is a single integer: r.

Output

For each test cases, give your answer in a single line.

Sample Input

2
42
97

Sample Output

6
9

Hint

For the first test case, the solutions are:

   x   y   z
   4   5   1
   4   1   5
   5   4   1
   5   1   4
   1   4   5
   1   5   4

Source

Tianjing Univ. Campus Contest 2008
<Submit>   <Statistics>   <Discuss>
 


Powered by Zhang Zhaoning PDL College of Computer
Since 2006.03.09 | 2007.11.22 | 2010.03.02 Copyright (r) 2006 - 2010 All Rights Reserved