HS08EQ - Amazing equality

The definition of a perfect number is about 2300 years old. A perfect number is defined as a positive integer which is the sum of its proper positive divisors, that is, the sum of the positive divisors excluding the number itself. What can we get if, in the sum, we replace each divisor by its square? You can prove that there is no such number. But there are many numbers for which the sum of some divisors' squares is equal to n, so n=d12+d22+...+dk2, where d1, d2, ...,dk are distinct (positive) divisors of n. You have to count how many times this happens. For example: the divisors of n=120 are 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120. And there are exactly two amazing equalities:
120=22+42+102
120=22+42+62+82

Input

The first number is T, denoting the number of test cases (T<1000). T lines follow, each of which contains one positive integer (n<1010).

Output

Output T lines, the answer for each n.

Example

Input:
6
120
720
1000
1200
92070
123618780

Output:
2
13
0
10
6448
292

Added by:Robert Gerbicz
Date:2009-04-09
Time limit:1.450s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Resource:High School Programming League 2008/09

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.