An đang học mật mã hóa. Cô ấy có phương trình \(a^x \equiv b \pmod{p}\) với \(p\) là số nguyên tố. An muốn tìm số mũ \(x\) nhỏ nhất để thỏa mãn phương trình này. Nếu không có nghiệm, in ra \(-1\).

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

• Một dòng chứa ba số nguyên \(a, b, p\) (\(2 \le p \le 10^9\), \(p\) nguyên tố, \(0 \le a, b < p\)).

Định dạng đầu ra

• Một số nguyên là \(x\) nhỏ nhất thỏa mãn, hoặc \(-1\) nếu không có.

Ví dụ

Input:

2 3 7

Output:

5

Giải thích: \(2^5 = 32 \equiv 3 \pmod{7}\).

Ràng buộc

• 50% số điểm: \(p \le 10^6\).
• 50% số điểm còn lại: \(p \le 10^9\).