Bình đang học về cấu trúc nhóm trong đại số. Cho số nguyên tố \(p\) và số \(a\), Bình muốn tìm bậc (order) của \(a\) modulo \(p\), tức là số nguyên dương \(d\) nhỏ nhất sao cho \(a^d \equiv 1 \pmod{p}\).

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

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

Định dạng đầu ra

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

Ví dụ

Input:

2 7

Output:

3

Giải thích: \(2^1 = 2, 2^2 = 4, 2^3 = 8 \equiv 1 \pmod{7}\), nên bậc là 3.

Ràng buộc

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