Quadratic Residue

In 1801, Carl Friedrich Gauss (1777-1855) published "Disquisitiones Arithmeticae", which laid the foundations of modern number theory and is still in print today. One of the topics it treats most often is the quadratic residue.

You are given a prime $p$ and an integer $a$ with $a \not\equiv 0 \pmod{p}$. For $a$ to be a quadratic residue modulo $p$, there must exist an integer $x$ such that

$x^2 \equiv a \pmod{p}$

Legendre (1752-1833) introduced the following Legendre symbol.

$\left(\frac{a}{p}\right) = \begin{cases} 1 & a \text{ is a quadratic residue mod } p \\ -1 & a \text{ is not a quadratic residue mod } p \end{cases}$

The Legendre symbol can be computed using the following properties, which hold only for distinct odd primes $p$, $q$ and integers $a$, $b$ not divisible by $p$.

1. $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$
2. $\left(\frac{1}{p}\right) = 1$
3. $a \equiv b \pmod{p} \Rightarrow \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$
4. $\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}, \quad \left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$
5. $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{(p-1)(q-1)/4}$

For example, the Legendre symbol can be computed as follows.

$\left(\frac{29}{79}\right) = (-1)^{78\cdot28/4} \left(\frac{79}{29}\right) = \left(\frac{79}{29}\right) = \left(\frac{-8}{29}\right) = \left(\frac{-1}{29}\right) \left(\frac{2}{29}\right)^{3} = \left(\frac{-1}{29}\right) \left(\frac{2}{29}\right) = (-1)^{28/2}(-1)^{(29^2-1)/8} = (-1)^{14}(-1)^{105} = -1$

The input consists of several test cases. The first line contains the number of test cases $T$. Each of the following test cases consists of two integers $a$ and $p$. Here $p$ $(2 < p < 10^9)$ is an odd prime, and $a$ satisfies $a \not\equiv 0 \pmod{p}$ and $\left| a \right| \le 10^9$.

For each test case, print "Scenario #i:" on the first line, where $i$ is the test case number starting from 1. On the next line, print the value of the Legendre symbol $\left(\frac{a}{p}\right)$ (either 1 or -1). Print one blank line between the outputs of consecutive test cases.