竞争用情

题目描述

橙子不想写题目背景了，她给你两个整数 $D,M$，让你判断是否存在 $[1,10^{18}]$ 之中的正整数 $x$ 使得 $x^x\equiv D\pmod M$。

如果存在，请给出任意一个 $x$。

输入格式

本题具有多组测试数据。

第一行一个长度为 $5$ 的 $01$ 串，第 $i$ 个字符为 $1$ 代表这个测试点所有数据具有第 $i$ 个特殊性质（见数据范围）。

第二行一个整数 $T$，表示数据组数。

对每组数据，一行两个整数 $D,M$，含义见上。

输出格式

对每组数据，若不存在 $x$，输出 $-1$，否则输出任意一个满足条件的 $x$。

样例输入 1

00000
10
1 6
2 9
3 8
4 16
5 20
6 72
7 998244353
114514 1919810
998244353 998844233
1523351 531341151

样例输出 1

49
41
51
2
45
-1
996491781308678145
-1
599187676736393
141803254889604071

数据范围

对于所有数据：$1\le T\le666$，$1\le M\le10^9$，$0\le D\le M$。

本题采用捆绑测试，并且开启所有合理的子任务依赖。

特殊性质：

• A：$M\le100$。
• B：$M=p^k$，其中 $p$ 是质数，$k$ 是正整数。
• C：$\mu(M)\ne0$。
• D：$M$ 与 $D$ 互质。
• E：保证 $x$ 存在。

提示

如果你拥有合理有效的算法，请相信常数。