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的阶。