Problem Description

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.

Input Format

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 Format

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

1
5 0

9

Hint

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$.

Translated by ChatGPT 5