You are given an integer N.

You are asked to find total number of integer pairs (A,B) such that
1 ≤ A,B ≤ N
A^{2}+B^{2}+gcd^{2}(A,B)+lcm^{2}(A,B)=N. Note that gcd^{2}(A, B) and lcm^{2}(A, B) denote the square of [gcd] and the square of [lcm] of numbers A and B respectively.

------ Input Format ------

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• The only line of each test case contains an integer N.

------ Output Format ------

For each test case, output in a single line, number of valid pairs (A,B).

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$4 ≤ N ≤ 10^{10}$
- Sum of $N$ over all test cases does not exceed $10^{10}$.

----- Sample Input 1 ------
3
4
10
20

----- Sample Output 1 ------
1
2
2

----- explanation 1 ------
Test case 1: The only valid pair is $(1, 1)$. Here:
- $1≤ 1 ≤ 4$.
- $1^{2} + 1^{2} + gcd^{2}(1,1) + lcm^{2}(1,1) = 1+1+1+1=4$.

Test case 2: Only $2$ pairs are possible. These are: $(1, 2)$ and $(2, 1)$.
- For pair $(1, 2)$: $1≤ 1, 2≤ 10$ and $1^{2}+2^{2}+gcd^{2}(1,2)+lcm^{2}(1,2)=1+4+1+4=10$.

Test case 3: Only $2$ pairs are possible. These are: $(1, 3)$ and $(3, 1)$.
- For pair $(1, 3)$: $1≤ 1, 3≤ 20$ and $1^{2}+3^{2}+gcd^{2}(1,3)+lcm^{2}(1,3)=1+9+1+9=20$.

见题面

见题面