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"。