505025 - 阶

【题目描述】阶(ord)

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

Input

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

Output

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

Examples

Input

2
1 3
2 3

Output

1
2
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题