题目描述

求关于 $\red x$ 的同余方程 $\red{ax \equiv 1 \pmod{b}}$ 的最小正整数解。

输入格式

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

输出格式

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

样例

输入样例

3 10

输出样例

7

提示

对于 $\red{40\%}$ 的数据，有 $\red{2 \leq b \leq 1\,000}$；

对于 $\red{60\%}$ 的数据，有 $\red{2 \leq b \leq 50\,000\,000}$；

对于 $\red{100\%}$ 的数据，有 $\red{2 \leq a, b \leq 2\,000\,000\,000}$。