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

内存限制：256 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：0 解决：0

题目描述

给定 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) (a−p)(b−p) 整除。

输入格式

第一行一个数 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×10​3​​；
对于 40% 40\% 40% 的数据，1<p<106 1 < p < 10 ^ 6 1<p<10​6​​；
对于 100% 100\% 100% 的数据，1<p<1012;1≤t≤5 1 < p < 10 ^ {12}; 1 \leq t \leq 5 1<p<10​12​​;1≤t≤5。