Background

These are just some simple quadratic congruence equations:)

Description

Provided several pairs of $p$ and $x$, we want to solve the congruence equation $a^2 + b^2 \equiv x \bmod p$ for $a$ and $b$. We want to know the number of solutions given that $a$ and $b$ are integers between $0$ and $p - 1$. Here we guarantee that $p$ is an odd number and is not divisible by any square numbers.

Input Format

Read from standard input.

The first line contains an integer $n$, representing the number of queries.

The following $n$ lines contains on each of them two integers $p$ and $x$ separated by a space.

We guarantee that $0 \leq x \leq p-1$, $p$ is an odd number, and for any odd prime $q \mid p$, we have $q^2 \nmid p$.

Output Format

Write to the standard output.

The output contains $n$ lines. The $i$ th line contains an integer representing the number of solutions of the $i$ th equation.

Sample

Input

1
5 0

Output

9

Explanation

The 9 solutions are $(a,b) = (0,0), (1,2), (1,3), (2,1), (2,4), (3,1), (3,4), (4,2), (4,3)$。

Sample 2

See ex_2.in and ex_2.ans in the attachments.

Subtasks

For all tasks, $n \leq 10^5$, $p \leq 10^6$，and $2 \nmid p$, $\forall$ odd prime $q \mid p$, $q^2 \nmid p$, $0 \leq x \leq p-1$.