题目描述

学校门禁系统使用两个正整数 $a,b$ 来校验一个编号 $x$。有效编号需要满足：$a\times x$ 除以 $b$ 的余数为 $1$。

请你求出满足条件的最小正整数 $x$。题目保证一定存在解。

输入格式

输入一行，包含两个正整数 $a,b$。

输出格式

输出一行一个正整数，表示最小正整数解 $x$。

3 10

7

数据范围

对于 $40\%$ 的数据，$2\le b\le 1000$；

对于 $60\%$ 的数据，$2\le b\le 50000000$；

对于 $100\%$ 的数据，$2\le a,b\le 2000000000$。