Naive Quadratic Congruence Equation

Given several pairs of positive integers \(p\) and \(x\), where \(p\) is an odd square-free number, count the number of solutions \((a,b)\) modulo \(p\) to the equation

[ a^2 + b^2 \equiv x \pmod{p}, ]

Here, the solutions \(a\) and \(b\) are taken from the set \(\{0, 1, 2, \ldots, p-1\}\). The task is to compute the number of pairs \((a,b)\) satisfying this congruence.

Note: Since \(p\) is square-free and odd, you can use a simple brute-force solution for small values of \(p\).

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each of the next \(T\) lines contains two positive integers \(p\) and \(x\), separated by a space.

\(p\) is an odd, square-free positive integer, and \(x\) is a positive integer.

outputFormat

For each test case, output the number of pairs \((a, b)\) (with \(0 \le a, b < p\)) that satisfy the equation \(a^2+b^2 \equiv x \pmod p\). Output each answer on a new line.

sample

3
7 2
7 5
11 1

8
8
12