Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:512 MB
统计

题目描述

给定正整数 $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 无特殊限制

大样例