题目背景
这就是一些朴素的二次同余方程:)
题目描述
给出若干组正整数 $p$ 和 $x$，求方程 $a^2 + b^2 \equiv x \bmod p$ 关于 $a$ 和 $b$ 在模 $p$ 意义下解的组数，其中 $p$ 是奇数，且不包含平方因子。
输入格式
从标准输入读入数据。
第一行包含一个正整数 $n$，表示询问个数。
接下来 $n$ 行每包含两个用空格分隔的正整数 $p$ 和 $x$，保证 $0 \leq x \leq p-1$，$p$ 是一个奇数，且对任意奇素数 $q \mid p$，都有 $q^2 \nmid p$。
输出格式
输出到标准输出。
输出包含 $n$ 行，第 $i$ 行包含一个正整数，表示第 $i$ 个方程解的组数。
样例
输入
1
5 0输出
9解释
9组解分别为 $(a,b) = (0,0), (1,2), (1,3), (2,1), (2,4), (3,1), (3,4), (4,2), (4,3)$。
样例二
见下载目录下的 ex_2.in 与 ex_2.ans。
子任务
每个测试点的分值为 $5$ 分。
对于所有数据，$n \leq 10^5$，$p \leq 10^6$，且 $2 \nmid p$，$\forall$ 奇素数 $q \mid p$，$q^2 \nmid p$，$0 \leq x \leq p-1$。
| 测试点 | $n \leq $ | $p \leq $ | 附加限制 |
|---|---|---|---|
| 1 | $≤5$ | $< 10^{2}$ | p为奇素数 |
| 2 | $≤10$ | $< 10^{3}$ | |
| 3 | / | ||
| 4 | $≤50$ | $< 10^{4}$ | p为奇素数 |
| 5 | $≤10^{2}$ | ||
| 6 | $≤50$ | / | |
| 7 | $≤10^{2}$ | ||
| 8 | |||
| 9 | $≤10^{3}$ | $< 10^{6}$ | p为奇素数 |
| 10 | / | ||
| 11 | |||
| 12 | $≤10^{5}$ | p为奇素数 | |
| 13 | / | ||
| 14 | |||
| 15 | |||
| 16 | |||
| 17 | $< 10^{7}$ | ||
| 18 | |||
| 19 | |||
| 20 |