题目描述

给定素数 $p$ ，$T$ 次询问使得 $a, b$ 满足 $a^x \equiv b \pmod p$ 的最小非负整数 $x$。

输入格式

第一行包括两个正整数 $T$ 和 $p$。

接下来 $T$ 行，每行包括两个正整数，表示一组询问。

输出格式

输出共 $T$ 行，每行包括一个非负整数，表示这个最小的 $x$，无解输出 $-1$。

样例

15 83
32 20
55 48
76 65
14 38
57 43
24 59
47 27
6 28
18 30
1 82
44 27
40 42
47 78
77 45
52 62

55
24
54
60
13
42
70
8
12
-1
2
-1
60
-1
69

数据范围与提示

对于 $20\%$ 的数据，$p < 10^3$。

对于 $40\%$ 的数据，$p < 10^{8}$。

对于 $60\%$ 的数据，$p < 10^{12}$。

对于 $80\%$ 的数据，$p < 10^{18}$。

对于 $100\%$ 的数据，$1 \le T \le 200, 2 \leq p < 3 \times 10^{18}$ 且 $p$ 为素数。