2710 - 同余方程

通过次数

0

提交次数

1

Time Limit : 1 秒
Memory Limit : 128 MB

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

Input

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

Output

15654206932985.png

Examples

Input

3 10

Output

7

Hint

【数据规模】

15654207153449.png

Source

一本通提高