Find the smallest positive integer solution $x$ to the congruence equation $ax \equiv 1 \pmod b$.

Input

The input consists of a single line containing two positive integers $a$ and $b$, separated by a space.

Output

The output consists of a single line containing a positive integer $x_0$, which is the smallest positive integer solution. It is guaranteed that a solution exists.

Examples

Input 1

3 10

Output 1

7

Constraints

For $40\%$ of the data, $2 \le b \le 1,000$;

For $60\%$ of the data, $2 \le b \le 50,000,000$;

For $100\%$ of the data, $2 \le a, b \le 2,000,000,000$.