A92142.「CodePlus #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$ 个方程解的组数。

每个测试点的分值为 $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$