题目描述

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

输入格式

一行两个正整数 $a$ 和 $b$，用空格隔开。

输出格式

一行一个正整数 $x_0$，表示最小正整数解。数据保证有解。

3 10

7

数据规模与约定

对于全部的测试点，保证 $2 \leq a, b \leq 2 \times 10^9$，且保证有解。

本题改编自 NOIP 2012 提高组