Cho 2 số nguyên dương ~a,m~ tìm một số nguyên dương ~x \leq 10^{18}~ sao cho ~a^x \equiv x~ (mod ~m~), nếu không tìm được in ra ~-1~.

Input

Dòng đầu tiên chứa 2 số nguyên dương ~a, m~.

Output

Một số nguyên dương ~x~ duy nhất. Nếu có nhiều ~x~ thỏa mãn, bạn có thể in ~x~ bất kỳ.

Ví dụ:

Input:

3 5

Output:

7

Subtask

• Subtask #1: ~50\%~ ~1 \leq a, m \leq 10^3~.
• Subtask #2: ~50\%~ ~1 \leq a, m \leq 10^9~.