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}\).