Hãy trả lời \(Q\) (\(1\le Q\le 10^5\)) truy vấn độc lập, mỗi truy vấn có dạng sau:

Bạn được cho bốn số nguyên \(a,b,c,d\) (\(-10^{18}\le a,b,c,d\le 10^{18}\)). Trong một thao tác, bạn có thể thực hiện \(a\mathrel{+}=b\) hoặc \(b\mathrel{+}=a\). Hãy xác định số thao tác tối thiểu để biến đổi \((a,b)\) thành \((c,d)\); nếu không thể, in ra \(-1\).

Dữ liệu vào

Dòng đầu tiên chứa \(Q\).

\(Q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(a,b,c,d\).

Dữ liệu ra

In đáp án cho mỗi truy vấn trên một dòng riêng.

Ví dụ

4
5 -3 -1 -3
5 3 5 2
5 3 8 19
5 3 5 3

2
-1
3
0

Phân nhóm

• Dữ liệu 2: \(|a|,|b|,|c|,|d|\le 10\).
• Dữ liệu 3: \(a,b\ge 0\).
• Dữ liệu 4: \(a\geq 0\geq b\).
• Dữ liệu 5: \(a\leq 0\leq b\).
• Dữ liệu 6: \(a,b\le 0\).
• Dữ liệu 7: \(c,d\ge 0\).
• Dữ liệu 8: \(c\geq 0\geq d\).
• Dữ liệu 9: \(c\leq 0\leq d\).
• Dữ liệu 10: \(c,d\le 0\).
• Dữ liệu 11–14: \(Q\leq 10^3\).
• Dữ liệu 15–19: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 February Contest, Platinum — Transforming Pairs. Tác giả: Benjamin Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1501