Description

Find the smallest positive integer $x$ such it satisfies the congruence equation $ax \equiv 1 \pmod{b}$.

Input Format

The input is only one line, containing two positive integers $a, b$ separated by a space.

Output Format

The output is only one line and contains a positive integer $x_0$, that is, the smallest positive integer solution. The input data is guaranteed to have a solution.

3 10

7

Constraints

For $40\%$ data, $2 \leq b \leq 10^3$.
For $60\%$ data, $2 \leq b \leq 5 \times 10^7$.
For $100\%$ data, $2 \leq a, b\leq 2 \times 10^9$.