测试数据来自 system/1781

描述

求关于 \(x\) 的同余方程 \(ax\equiv 1(\operatorname{mod}~b)\)的最小正整数解。

格式

输入格式

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

输出格式

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

样例

样例输入1

3 10

样例输出1

7

提示

对于 \(40\%\) 的数据，\(2\leq b\leq 10^3\)；
对于 \(60\%\) 的数据，\(2\leq b\leq 5\times 10^7\)；
对于 \(100\%\) 的数据，\(2\leq a,b\leq 2\times 10^9\)。