Trên một sợi dây dài vô hạn, được mô tả như một trục số nguyên, có 3 con kiến \(A, B, C\) lần lượt đứng ở các vị trí \(x1, x2\) và \(x3\) vào thời điểm ban đầu. Sau đó chúng bắt đầu di chuyển và vào thời điểm cuối cùng khoảng cách giữa mỗi cặp kiến nhỏ nhất là \(d\).

Ba con kiến không di chuyển cùng lúc. Trong một giây, chỉ có một con kiến có thể thay đổi vị trí của mình. Sau mỗi giây, con kiến di chuyển chỉ có thể ở cách vị trí cũ của nó một khoảng chính xác bằng 1 (sang bên trái hoặc bên phải vị trí cũ). Cả 3 con kiến có thể ở cùng một vị trí cùng một lúc và có thể "đi ngang qua nhau".

Bạn cần tìm số giây tối thiểu cần thiết để khoảng cách giữa mỗi cặp kiến không nhỏ hơn \(d\). Tọa độ của kiến có thể âm, vì sợi dây dài vô hạn về cả hai đầu.

Bạn phải trả lời \(q\) truy vấn độc lập

Dữ liệu vào

• Dòng đầu tiên của đầu vào chứa một số nguyên \(q (1 \leq q \leq 1000)\) là số lượng truy vấn.
• \(q\) dòng sau, mỗi dòng chứa một truy vấn gồm 4 số nguyên \(x1, x2, x3, d (1 \leq x1, x2, x3, d \leq 10^9)\). Các số viết cách nhau một dấu cách.

Kết quả

• Chương trình của bạn cần in ra \(q\) dòng, dòng thứ \(i\) là câu trả lời cho truy vấn thứ \(i\).

Ví dụ 1:

INPUT

4
5 2 6 3
3 1 5 6
8 3 3 2
2 3 10 4

OUTPUT

2
8
2 
3

Giải thích:

• Truy vấn đầu tiên: trong hai giây đầu tiên, con kiến C (ở vị trí 6) di chuyển 2 đơn vị sang phải (đến vị trí 8) - mất 2 giây, trong khi A và B giữ nguyên vị trí của chúng. Lúc này, khoảng cách giữa A và B là |5 - 2| = 3, khoảng cách B và C là |2 - 8| = 6 và khoảng cách giữa A và C là |5 - 8| = 3. Cả ba khoảng cách đều không nhỏ hơn \(d = 3\), như vậy số giây tối thiểu để chúng có khoảng cách này là 2.