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.