[Code+#7]同余方程

题目描述

这就是一些朴素的二次同余方程:) ------------------ 给出若干组正整数 $p$ 和 $x$,求方程 $a^2+b^2\equiv x {\pmod p}$ 关于 $a$ 和 $b$ **在模 $\boldsymbol p$ 意义下**解的组数,其中 $p$ 是奇数,且不包含平方因子。

输入输出格式

输入格式


第一行包含一个正整数 $n$,表示询问个数。 接下来 $n$ 行每包含两个用空格分隔的正整数 $p$ 和 $x$,保证 $0 \le x \le p - 1$,$p$ 是一个奇数,且对任意奇素数 $q\mid p$,都有 $q^2 \nmid p$。

输出格式


输出包含 $n$ 行,第 $i$ 行包含一个正整数,表示第 $i$ 个方程解的组数。

输入输出样例

输入样例 #1

1
5 0

输出样例 #1

9

说明

### 样例解释 $9$ 组解分别为 $(a,b) = (0,0),(1,2),(1,3),(2,1),(2,4),(3,1),(3,4),(4,2),(4,3)$。 ### 子任务 每个测试点的分值为 $5$ 分。 **对于所有数据**,$n\le 10^5$,$p\le10^7$,且 $2\nmid p$,$\forall$ 奇素数 $q\mid p,q^2\nmid p$,$0\le x\le p-1$。 | 测试点编号 | $n\le$ | $p\le$ | 附加性质 | | :--------: | :----: | :----: | :------------: | | $1$ | $5$ | $100$ | $p$ 为奇素数 | | $2$ | $10$ | $10^3$ | $p$ 为奇素数 | | $3$ | $10$ | $10^3$ | | | $4$ | $50$ | $10^4$ | $p$ 为奇素数 | | $5$ | $100$ | $10^4$ | $p$ 为奇素数 | | $6$ | $50$ | $10^4$ | | | $7$ | $100$ | $10^4$ | | | $8$ | $100$ | $10^4$ | | | $9$ | $10^3$ | $10^6$ | $p$ 为奇素数 | | $10$ | $10^3$ | $10^6$ | | | $11$ | $10^3$ | $10^6$ | | | $12$ | $10^5$ | $10^6$ | $p$ 为奇素数 | | $13$ | $10^5$ | $10^6$ | | | $14$ | $10^5$ | $10^6$ | | | $15$ | $10^5$ | $10^6$ | | | $16$ | $10^5$ | $10^6$ | | | $17$ | $10^5$ | $10^7$ | | | $18$ | $10^5$ | $10^7$ | | | $19$ | $10^5$ | $10^7$ | | | $20$ | $10^5$ | $10^7$ | |