← 返回题目列表

AtCoder · tenka1_2017_f

F. 模块化功率方程!!

中文机器翻译题面 查看原题

分数: 1400 点

问题陈述

处理 Q 查询如下。

  • 给你两个整数 A_i 和 M_i。判断是否存在正整数 K_i 不超过 2 × 10^{18} 这样 A_i^{K_i} ≡ K_i (mod M_i),如果存在则查找一个。

约束

  • 1 \leq Q \leq 100
  • 0 \leq A_i \leq 10^9(1 \leq i \leq Q)
  • 1 \leq M_i \leq 10^9(1 \leq i \leq Q)

输入

输入由标准输入按以下格式给出:

Q
A_1 M_1
:
A_Q M_Q

输出

在 i第行,打印 -1 如果没有整数 K_i 满足条件。 否则,打印一个整数 K_i 不超过 2 × 10^{18} 这样 A_i^{K_i} ≡ K_i (mod M_i)。如果有多个解决方案,则任何一个都将被接受。


示例输入 1

4
2 4
3 8
9 6
10 7

示例输出 1

4
11
9
2

可见满足条件: 2^4 = 16 ≡ 4 (mod 4), 3^{11} = 177147 ≡ 11 (mod 8), 9^9 = 387420489 ≡ 9 (mod 6) 和 10^2 = 100 ≡ 2 (mod 7).


示例输入 2

3
177 168
2028 88772
123456789 987654321

示例输出 2

7953
234831584
471523108231963269