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