504035 - 乘法逆元

【题目描述】乘法逆元(inv)

a-1≡x (mod m)等价于ax≡1 (mod m),试求a关于m的最小的正数逆元。

输入

有多组数据,第一行为一个整数T( T≈2 000)表示组数。随后每组数据有两个整数a(0<a≤1000)和m(0<m≤1000)。

输出

输出x的最小值,若不存在,输出"Not Exist"。

样例

输入

3
3 11
4 12
5 13

输出

4
Not Exist
8
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题