题目描述

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

输入格式

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

输出格式

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

样例数据

input

3 10

output

7

数据规模与约定

时间限制：$1 \text{s}$

空间限制：$256 \text{MB}$