时间限制：1秒　　内存限制：256M

---

【问题描述】

　　求关于 \(x\) 的同余方程 \(ax ≡ 1 (mod\ b)\) 的最小正整数解。

【输入格式】

　　输入只有一行，包含两个正整数 \(a, b\)，用一个空格隔开。

【输出格式】

　　输出只有一行，包含一个正整数，即最小正整数解。输入数据保证一定有解。

【输入输出样例】

　Input

3 10

　Output

7

【数据说明】

　　对于 \(40\%\) 的数据，\(2 ≤ b ≤ 1,000\)；
　　对于 \(60\%\) 的数据，\(2 ≤ b ≤ 5,000,000\)；
　　对于 \(100\%\) 的数据，\(2 ≤ b ≤ 2,000,000,000\)；

【来源】

　　Mr.he