配点 : 800 点
問題文
T 案例的以下问题。 给出了
正整数 A,M 。 对于 A^k \equiv k \pmod M 的非负整数 查找 k\ (k < M \times \varphi (M)) 的数量 (ans ),满足条件 k 该值应乘以 \min(ans,1000) 请构建一个。
但是, 运算前设定中包含的 \varphi(M) 是 您也可以写欧拉 phi 函数 代表。
制約
- 1 \le T \le 100
- 1 \leq A,M \leq 10^9
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个案例均按以下格式给出。 打印
A M
出力
2T 行。 2i-1 减去 2i 行中, \mathrm{case}_i 的答案。
对于每种情况,它都在问题陈述的第一行中定义。 ans 下一行用空格分隔满足条件 k 该值应乘以 \min(ans,1000) 。
但是,输出 k 必须全部不同。
入力例 1
1 2 4
出力例 1
1 4
2^4\equiv 4 \pmod 4 。
原案: 海龟0123__