You are given two numbers: $a$ and $M$. Your task is to find $x$ such that $a\cdot x \equiv 1 \pmod{M}$ and $0 < x < M$ or report that such number doesn't exist.

Input

The only line consists of the numbers $a$ and $M$.

Output

The output consists of one integer: $x$ if it exists or -1 if such $x$ doesn't exist.

Constraints

• $0 \leq a < m \leq 10^9$

Example

Input:

3 5

Output:

2

Explanation: $3 \cdot 2 = 6 \equiv 1 \pmod{5}$

Input:

4 6

Output:

-1

Explanation: $4\cdot x$ is either 0, 2 or 4 modulo 6 for any $x$.