Tìm nghiệm nguyên dương nhỏ nhất của phương trình đồng dư:

\[ a \cdot x \equiv 1 \pmod{b} \]

Tức là, tìm số nguyên dương \(x\) nhỏ nhất sao cho \(a \cdot x\) chia cho \(b\) dư 1.

Định dạng vào

• Một dòng gồm hai số nguyên \(a, b\) cách nhau bởi dấu cách.

Định dạng ra

• Một số nguyên: nghiệm nguyên dương nhỏ nhất \(x_0\) thỏa mãn phương trình.
• Dữ liệu đảm bảo luôn tồn tại nghiệm.

Input

3 10

Output

7

Giải thích

\(3 \cdot 7 = 21 \equiv 1 \pmod{10}\)

Ràng buộc dữ liệu

• Với 40% dữ liệu: \(2 \le b \le 1\,000\)
• Với 60% dữ liệu: \(2 \le b \le 50\,000\,000\)
• Với 100% dữ liệu: \(2 \le a, b \le 2\,000\,000\,000\)