内存限制：512 MiB
时间限制：1000 ms
标准输入输出
题目类型：VJudge（洛谷）
评测方式：VJudge
上传者：
匿名
对于正整数 ，请求出有多少个有序整数对 ，使得 。答案对 取模。
本题有多组数据。
第一行一个整数 ，表示数据组数。
对于每组数据，一行一个正整数，表示 的值。
输出共 行。
第 行一个非负整数，表示第 组数据的答案对 取模后的值。
样例输入 1
10
4
1000
200000
802241960520
999999999937
49770428644836900
250000006000000027
729021870143100133
900000000000000017
907000000000033559
样例输出 1
24
3744
93744
59948653
999943511
821944886
26
729842040
600000501
152276389
对于所有数据，。
对于样例一的第一组数据，以下均为符合题意的 （此处没有列出所有可行的数对）。
