Description

For a positive integer $n$, find the number of ordered quadruples of integers $(a,b,c,d)$ such that $a^2+b^2+c^2+d^2=n$. The answer is taken modulo $10^9+7$.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case, one line contains a positive integer, representing the value of $n$.

Output Format

Output a total of $T$ lines.

On the $k$-th line, output a non-negative integer, which is the answer for the $k$-th test case modulo $10^9+7$.

10
4
1000
200000
802241960520
999999999937
49770428644836900
250000006000000027
729021870143100133
900000000000000017
907000000000033559

24
3744
93744
59948653
999943511
821944886
26
729842040
600000501
152276389

Hint

Test point ID	Limit
$1\sim 3$	$n\le 2\times 10^5$
$4\sim 6$	$n\le 10^{12}$
$7\sim 10$	None

For all testdata, $1\le n\le 10^{18},1\le T\le 50$.

For the first test case of Sample 1, the following are all valid $(a,b,c,d)$ (not all feasible quadruples are listed here).

$$(1,1,1,1),(1,1,1,-1),(-1,-1,-1,-1),(2,0,0,0),(0,-2,0,0)$$

Translated by ChatGPT 5