P2019 Four Squares Theorem

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$.

**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 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$.

| 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