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=d₁²+d₂²+...+d_k², where d₁, d₂, ...,d_k 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=2²+4²+10²
120=2²+4²+6²+8²

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<10¹⁰).

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