本题没有可用的提交语言。

题目描述

背景

1801年，卡尔·弗里德里希·高斯（Carl Friedrich Gauss，1777-1855）发表了《算术研究》（Disquisitiones Arithmeticae），这部著作奠定了现代数论的基础，至今仍在出版。书中探讨的众多课题之一就是二次剩余问题。

对于一个素数 $p$ 和一个整数 $a \not\equiv 0 \pmod{p}$，如果存在整数 $x$ 使得：

则称 $a$ 是模 $p$ 的二次剩余（quadratic residue），否则称为二次非剩余（quadratic non-residue）。拉格朗日（Lagrange，1752-1833）引入了以下符号，称为勒让德符号（Legendre symbol）：
计算勒让德符号有以下规则，这些规则仅适用于不同的奇素数 $p, q$ 以及不被 $p$ 整除的整数 $a, b$：

其中：

• 规则1到3是定义中的直接推论；
• 规则4被称为补充定理（Completion Theorem）；
• 规则5是著名的二次互反律（Law of Quadratic Reciprocity），高斯本人在《算术研究》中为此给出了不少于六种不同的证明。

利用这些规则，可以计算所有可能的勒让德符号，例如：

输入

第一行包含测试用例的数量。
对于每个测试用例，有一行包含两个整数 $a$ 和 $p$，用一个空格隔开。其中：

• $2 < p < 10^9$ 是一个奇素数；
• $a$ 满足 $a \not\equiv 0 \pmod{p}$ 且 $|a| \leq 10^9$。

输出

对于每个测试用例：

1. 首先输出一行 Scenario #i:，其中 $i$ 是测试用例的编号（从1开始）；
2. 然后输出一行，包含勒让德符号 $\left( \frac{a}{p} \right)$；
3. 最后输出一个空行。

示例输入 1

3
29 79
2 29
1 3

示例输出 1

Scenario #1:
-1

Scenario #2:
-1

Scenario #3:
1

来源
TUD Programming Contest 2003, Darmstadt, Germany