Bessie, cô bò thông thái, vừa khám phá ra một niềm say mê mới — phép thuật toán học! Một ngày nọ, khi đang chạy qua những cánh đồng trong trang trại của Farmer John, cô bắt gặp hai đống cỏ khô bị phù phép. Đống thứ nhất có \(a\) kiện và đống thứ hai có \(b\) kiện (\(1\le a,b\le 10^{18}\)).

Bên cạnh đống cỏ, bị vùi một nửa trong đất, cô tìm thấy một cuộn giấy cổ. Khi cô mở nó ra, những ký tự phát sáng hé lộ một lời tiên tri:

Để thực hiện sắc lệnh của Đại Đồng Cỏ, người được chọn phải biến đổi hai đống cỏ nhỏ bé này thành chính xác \(c\) và \(d\) kiện — không hơn, không kém.

Bessie nhận ra cô chỉ có thể thi triển hai phép thuật sau:

• Cô có thể triệu hồi thêm số kiện cỏ vào đống thứ nhất bằng đúng số kiện hiện có trong đống thứ hai.
• Cô có thể triệu hồi thêm số kiện cỏ vào đống thứ hai bằng đúng số kiện hiện có trong đống thứ nhất.

Cô phải thực hiện các thao tác tuần tự, nhưng có thể thực hiện chúng bao nhiêu lần và theo bất kỳ thứ tự nào. Cô phải đạt chính xác \(c\) kiện ở đống thứ nhất và \(d\) kiện ở đống thứ hai (\(1\le c,d\le 10^{18}\)).

Với mỗi trong số \(T\) (\(1\le T\le 10^4\)) trường hợp kiểm thử độc lập, hãy in ra số thao tác tối thiểu cần thiết để hoàn thành lời tiên tri; nếu không thể, in ra \(-1\).

Dữ liệu vào

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

\(T\) 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 ra \(T\) dòng, là đáp án cho từng trường hợp kiểm thử.

Ví dụ

4
5 3 5 2
5 3 8 19
5 3 19 8
5 3 5 3

-1
3
-1
0

1
1 1 1 1000000000000000000

999999999999999999

Phân nhóm

• Dữ liệu 3–4: \(\max(c,d)\le 20\cdot\min(a,b)\).
• Dữ liệu 5–7: \(T\le 10\) và \(a,b,c,d\le 10^6\).
• Dữ liệu 8–12: Không có ràng buộc bổ sung.

Nguồn

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

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