Cho hai số nguyên dương \(a\) và \(M\) với \(\gcd(a, M) = 1\). Tìm cấp (order) của \(a\) theo modulo \(M\), tức là số nguyên dương \(k\) nhỏ nhất sao cho \(a^k \equiv 1 \pmod{M}\).

Định dạng đầu vào

• Một dòng chứa hai số nguyên \(a, M\) (\(2 \le M \le 10^9\), \(1 \le a < M\), \(\gcd(a, M) = 1\)).

Định dạng đầu ra

• Một số nguyên duy nhất là cấp của \(a\) modulo \(M\).

Ví dụ

Input:

3 7

Output:

6

Giải thích: \(3^1=3, 3^2=2, 3^3=6, 3^4=4, 3^5=5, 3^6=1 \pmod{7}\). Cấp = 6.

Ràng buộc

• 100% số điểm: \(M \le 10^9\).