1399: #6064. 「2017 山东一轮集训 Day2」Number

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

给定 p p p(一个质数),问有多少对 a,b(a>p,b>p) a, b(a > p, b > p) a,b(a>p,b>p) 满足 ab ab ab(a−p)(b−p) (a - p)(b - p) (ap)(bp) 整除。

输入格式

第一行一个数 t t t,表示有多少组数据。
第二至 t+1 t + 1 t+1 行每行各一个数,表示这组数据的 p p p

输出格式

输出 t t t 行,每行一个数,表示对应数据的答案。

样例

样例输入

3
2
23
59

样例输出

14
80
116

数据范围与提示

对于 20% 20\% 20% 的数据,1<p<5×103 1 < p < 5 \times 10 ^ 3 1<p<5×103
对于 40% 40\% 40% 的数据,1<p<106 1 < p < 10 ^ 6 1<p<106
对于 100% 100\% 100% 的数据,1<p<1012;1≤t≤5 1 < p < 10 ^ {12}; 1 \leq t \leq 5 1<p<1012;1t5