P6610 [Code+#7] Congruence Equation

These are some naive quadratic congruence equations. ------------------ Given several groups of positive integers $p$ and $x$, find the number of solution pairs $(a,b)$ to the equation $a^2 + b^2 \equiv x {\pmod p}$ with respect to $a$ and $b$ **modulo $\boldsymbol p$**, where $p$ is odd and has no square factors.

The first line contains a positive integer $n$, indicating the number of queries. The next $n$ lines each contain two positive integers $p$ and $x$ separated by a space. It is guaranteed that $0 \le x \le p - 1$, $p$ is odd, and for any odd prime $q \mid p$, we have $q^2 \nmid p$.

Output $n$ lines. The $i$-th line contains a positive integer, indicating the number of solution pairs for the $i$-th equation.

### Sample Explanation The $9$ solution pairs are $(a,b) = (0,0),(1,2),(1,3),(2,1),(2,4),(3,1),(3,4),(4,2),(4,3)$. ### Subtasks Each test point is worth $5$ points. **For all testdata**, $n \le 10^5$, $p \le 10^7$, and $2 \nmid p$, $\forall$ odd primes $q \mid p, q^2 \nmid p$, $0 \le x \le p - 1$. | Test Point ID | $n \le$ | $p \le$ | Additional Property | | :-----------: | :-----: | :-----: | :-----------------: | | $1$ | $5$ | $100$ | $p$ is an odd prime | | $2$ | $10$ | $10^3$ | $p$ is an odd prime | | $3$ | $10$ | $10^3$ | | | $4$ | $50$ | $10^4$ | $p$ is an odd prime | | $5$ | $100$ | $10^4$ | $p$ is an odd prime | | $6$ | $50$ | $10^4$ | | | $7$ | $100$ | $10^4$ | | | $8$ | $100$ | $10^4$ | | | $9$ | $10^3$ | $10^6$ | $p$ is an odd prime | | $10$ | $10^3$ | $10^6$ | | | $11$ | $10^3$ | $10^6$ | | | $12$ | $10^5$ | $10^6$ | $p$ is an odd prime | | $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$ | | Translated by ChatGPT 5