题目描述

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

输入格式

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

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

输出格式

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

样例

input

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

output

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 $ 为素数。