暂无测试数据。

Background

本题是一道模板题

Description

已知\(p\)为素数。求方程
\[a^2 + b^2 = p\]
的整数解的数量

Format

Input

输入的第一行包含一个整数\(n\)
接下来有\(n\)个素数\(p\)。

Output

输出\(n\)个整数，表示各组数据解的数量。

Sample 1

Input

1
5

Output

8

Details

当\(p=5\)时，有8组解，分别为：
\[(1,2), (-1,2),(1,-2),(-1,-2),(2,1),(-2,1),(2,-1),(-2,-1)\]

Limitation

本题分为三部分：弱化数据（20%）、标准数据（20%）和全面数据（60%）
对于弱化数据，你可以暴力解决。
对于标准数据，你可以经过找规律解决，即使你的结论并不强力。
对于全面数据，你要严格分析出所有的条件。每个条件有一部分的分数。

弱化数据：2.0s的时限和512 MB的内存

对于40%的数据，\(n = 1\), \(p \leqslant 10^5\)
对于100%的数据，\(n = 1\), \(p \leqslant 10^{14}\)

标准数据：1.0s的时限和128 MB的内存

对于40%的数据，\(n \leqslant 10^5\), \(p \leqslant 10^9\)
对于100%的数据，\(n \leqslant 10^7\), \(p \leqslant 10^{18}\)

全面数据：1.0s的时限和128 MB的内存

对于25%的数据，\(n \leqslant 3\times 10^7\), \(p \leqslant 10^{18}\)
对于另外25%的数据，\(n \leqslant 10^7\), \(p \leqslant 10^{22}\)
对于100%的数据，\(n \leqslant 10^8\), \(p \leqslant 10^{5,000}\)