小多最近学习了一点数论。
最近她学习了阶这个概念，对算阶很有兴趣。
但是手算阶太难了，请你帮帮她。
给定一个质数 p，定义一个数 x(1 ≤ x < p) 模 p 的阶为：最小的正整数 t 使得 xt 模 p 等于 1（即 xt 除以 p 的余数为 1），可以证明：这样的正整数一定存在。
现在请你帮助小多算若干组阶。
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $4$ | 正确数量 | $7$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
小多最近学习了一点数论。
最近她学习了阶这个概念，对算阶很有兴趣。
但是手算阶太难了，请你帮帮她。
给定一个质数 p，定义一个数 x(1 ≤ x < p) 模 p 的阶为：最小的正整数 t 使得 xt 模 p 等于 1（即 xt 除以 p 的余数为 1），可以证明：这样的正整数一定存在。
现在请你帮助小多算若干组阶。
第一行一个正整数 T，代表接下来共有 T 个问题。
接下来 T 行，每行两个正整数 p 和 x，请回答 x 模 p 的阶。
7
2 1
3 1
3 2
5 1
5 2
5 3
5 4
1
1
2
1
4
4
2
【样例 1 解释】
以第一个和第五个为例。 第一个问题中 1 1 = 1，而 1 是最小的正整数，所以显然为答案。 第五个问题中 2 1 = 2, 2 2 = 4, 2 3 = 8 模 5 不为 1，2 4 = 16 模 5 为 1，因此 4 为答案。
【数据规模与约定】
对于 40% 的数据，满足 p ≤ 100。
对于 70% 的数据，满足 p ≤ 104。
对于 100% 的数据，满足 1 ≤ T ≤ 10, 1 ≤ x < p ≤ 105，保证 p 是质数。
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$7 $ms] | chengcary | 1090539 | 2024-04-02 10:47:56 |
| 内存最少[$2024 $KB] | 只能过个样例~~~ | 960235 | 2023-04-28 22:02:45 |
| 第一AC | 只能过个样例~~~ | 960235 | 2023-04-28 22:02:45 |
| 第一挑战 | 波士顿大龙虾 | 956821 | 2023-04-21 17:42:57 |
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|