Tèo có \(q\) truy vấn, mỗi truy vấn là phương trình \(a^x \equiv b \pmod{p}\) với \(p\) là số nguyên tố nhỏ (\(p \le 10^4\)). Hãy giúp Tèo tìm \(x\).

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

• Dòng đầu: \(q\) (\(1 \le q \le 100\)).
• \(q\) dòng tiếp: mỗi dòng \(a, b, p\).

Định dạng đầu ra

• \(q\) dòng, mỗi dòng là \(x\) hoặc \(-1\).

Ví dụ

Input:

1
2 3 7

Output:

5

Ràng buộc

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