题目描述
给定正整数 $a,m$，找到一个 $x$ 满足 $x\equiv a^x\pmod m$，并且 $1\le x\le 9\times 10^{18}$，或者报告无解。
输入格式
第一行一个正整数 $T$ 表示数据组数。每组数据两个正整数 $a,m$。
输出格式
$T$ 行，每行一个整数表示每组数据的答案。如果无解输出 -，否则输出一个满足条件的 $x$。
样例输入
17
2 40
3 42
4 44
5 47
6 69
7 77
8 63
9 64
10 30
11 27
12 38
13 83
14 70
15 21
16 59
17 32
18 49样例输出
16
27
100
8
108
14
64
9
10
23
64
44
56
15
26
17
67数据范围
对于所有数据，满足 $2\le a,m\le 10^9,1\le T\le 10^3$。
| 子任务编号 | 分值 | 其他限制 |
|---|---|---|
| 1 | 20 | $m\le 100$ |
| 2 | 20 | $m$ 是素数 |
| 3 | 20 | $a$ 是素数 |
| 4 | 40 | 无特殊限制 |