Thuật toán Tonelli-Shanks: Khai căn bậc hai modulo số nguyên tố

Mô tả bài toán

Cho một số nguyên N và một số nguyên tố lẻ P.

Phương trình đồng dư: X² ≡ N mod P Một số N được gọi là thặng dư bậc hai (quadratic residue) modulo P nếu tồn tại số nguyên X thỏa mãn phương trình trên.

Yêu cầu: Áp dụng Thuật toán Tonelli-Shanks để giải phương trình trên. Nếu phương trình có nghiệm, hãy in ra nghiệm X nhỏ nhất trong khoảng [0, P - 1]. Nếu vô nghiệm, in ra -1.

Dữ liệu vào

• Dòng đầu chứa số lượng bộ test T (1 ≤ T ≤ 1000).
• T dòng tiếp theo, mỗi dòng gồm hai số nguyên N, P (0 ≤ N < P, 3 ≤ P ≤ 10⁹, P là số nguyên tố lẻ).

Dữ liệu ra

• Với mỗi bộ test, in ra nghiệm X nhỏ nhất (0 ≤ X ≤ P - 1), hoặc -1 nếu không tồn tại.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.