505025 - 阶

【题目描述】阶(ord)

满足ar≡1 (mod n)的最小整数r,称为a模n的阶,这里a与n互质。试求r。

输入

第一行为一个数T,表示测试用例的数目(T<100000)。 接下来T行,每行输入两个整数a和n,a与n互质(1≤a<n≤1e9)。

输出

输出T行,每行一个表示a模n的阶。

样例

输入

2
1 3
2 3

输出

1
2
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题