Tý đang nghiên cứu về mật mã đường cong elliptic. Có \(q\) truy vấn, mỗi truy vấn cho \(a, b, p\) (\(p\) nguyên tố nhỏ). Tý cần tìm \(x\) nhỏ nhất thỏa \(a^x \equiv b \pmod{p}\).

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

• Dòng đầu: số nguyên \(q\) (\(1 \le q \le 100\)).
• \(q\) dòng tiếp: mỗi dòng \(a, b, p\) (\(p \le 10^4\), \(p\) nguyên tố).

Định dạng đầu ra

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

Ví dụ

Input:

2
2 3 7
2 1 7

Output:

5
0

Ràng buộc

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