题目描述

对于正整数 $n$，请求出有多少个有序整数对 $(a,b,c,d)$，使得 $a^2+b^2+c^2+d^2=n$。答案对 $10^9+7$ 取模。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据，一行一个正整数，表示 $n$ 的值。

输出格式

输出共 $T$ 行。

第 $k$ 行一个非负整数，表示第 $k$ 组数据的答案对 $10^9+7$ 取模后的值。

10
4
1000
200000
802241960520
999999999937
49770428644836900
250000006000000027
729021870143100133
900000000000000017
907000000000033559

24
3744
93744
59948653
999943511
821944886
26
729842040
600000501
152276389

提示

测试点编号	限制
$1\sim 3$	$n\le 2\times 10^5$
$4\sim 6$	$n\le 10^{12}$
$7\sim 10$	无

对于所有数据，$1\le n\le 10^{18},1\le T\le 50$。

对于样例一的第一组数据，以下均为符合题意的 $(a,b,c,d)$（此处没有列出所有可行的数对）。

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