Đồng dư tuyến tính

Với từng bộ $a, b, m$ , hãy giải đồng dư $a \cdot x$ ≡ $b (mod m)$ , hoặc báo vô nghiệm. Một $x$ hợp lệ khi $m$ chia $a \cdot x - b$ . Có thể in bất kỳ nghiệm nguyên nào.

Input

Dòng đầu chứa $T$ .
Mỗi trong $T$ dòng tiếp theo chứa $a, b$ và $m$ .

Output

Mỗi truy vấn in một nghiệm $x$ hoặc impossible.

Constraints

$1 \leq T \leq 1 0^{5} .$
$1 \leq a, b, m \leq 2 \cdot 1 0^{9} .$

Scoring

Subtask $1$ ( $50%$ số điểm): các test từ $1$ đến $10$ , dùng miền dữ liệu nhỏ để có thể đối chiếu độc lập.
Subtask $2$ ( $50%$ số điểm): không có giới hạn bổ sung ngoài các ràng buộc đã nêu.

Example

Test 1

Input

Output

2
impossible
2

Giải thích: Truy vấn đầu có nghiệm $2$ ; truy vấn thứ hai vô nghiệm vì $g cd (4, 6)$ không chia $3$ ; truy vấn cuối cũng cho nghiệm $2$ .

Lời giải tóm tắt

Ý tưởng: Đồng dư a·x≡b (mod m) tương đương với phương trình a·x+m·y=b. Gọi g=gcd(a,m). Nghiệm tồn tại khi và chỉ khi g chia b.
Ý tưởng: Euclid mở rộng cho một hệ số u thỏa a·u+m·v=g. Sau khi nhân với b/g, ta nhận một nghiệm của đồng dư. Chuẩn hóa nó modulo m/g để có đại diện không âm; nếu không thỏa điều kiện chia hết thì in impossible.
Ý tưởng: Mỗi truy vấn chạy trong O(log m); tổng thời gian O(T log M).