Sau khi dành dụm cả thanh xuân mỗi ngày ~5\$~, ~Capoo~ đã có khả năng mua được một chiếc flycam tầm trung dành cho người mới chơi mang tên DJI inspire 3 có giá chỉ xấp xỉ ~20.000\$~. ~Capoo~ rất phấn khởi, vừa mang về đã đập hộp và thử nghiệm tất cả các tính năng. Một hôm nọ, bản tính tò mò sẵn có đã thôi thúc cậu mèo đi nghịch chiếc flycam để xem thử giới hạn của nó. ~Capoo~ ra một cánh đồng trống như con tim anh ấy và bắt đầu bài thử nghiệm của mình.

Bài thử nghiệm ~Capoo~ bắt đầu bằng việc cậu sẽ cất cánh flycam tại vị trí có tọa độ ~L~ và đi theo một đường thẳng đến tọa độ ~R~. Trên hành trình của mình, cứ bay một khoảng ~D~ thì flycam sẽ bay qua một checkpoint. Mỗi khi bay qua một checkpoint có tọa độ ~x~, flycam sẽ gửi tín hiệu và tiêu thụ một lượng năng lượng là ~|K-x|~. Điểm ~L~ được xem là một checkpoint.

Tuy flycam xịn nhưng ~Capoo~ phát hiện rằng nó hoàn toàn không thể tính được tổng năng lượng đã tiêu thụ hết dẫn đến các rủi ro khi sử dụng. Ám ảnh bởi Toán học, chú mèo chúng ta không tài nào tính toán được vì vậy hãy giúp ~Capoo~ tính tổng năng lượng tiêu thụ của chiếc flycam trên quãng đường thí nghiệm nhé.

Dữ liệu vào

Gồm ~Q~ ~(1\le Q \le 50)~ dòng, mỗi dòng bao gồm 4 số nguyên ~L, R, D, K~.

• ~L, R~ là tọa độ đầu và cuối của đường thẳng mà ~Capoo~ bay thử nghiệm ~(1\le L\le R \le 10^6)~.
• ~D~ là khoảng cách để phát hiện một điểm là checkpoint ~(1 \le D \le R-L+1)~.
• Và cuối cùng ~K~ ~(1\le K \le 10^9)~ là vị trí ~Capoo~ đang đứng.

Kết quả ra

Gồm ~Q~ dòng, mỗi dòng là tổng năng lượng tiêu thụ của thí nghiệm tương ứng.

Ràng buộc

• Có ~50\%~ test tương ứng với ~50\%~ số điểm có ~Q \le 10 , 1\le L\le R \le 10^4 , D=1~.
• ~50\%~ test còn lại với ~50\%~ số điểm không có ràng buộc gì thêm.

Ví dụ 1

Dữ liệu

1
2 12 3 13

Kết quả

26

Giải thích

Trong ~[2;12]~ có các điểm checkpoint : ~2,5,8,11~ và tổng năng lượng là ~|13-2|+|13-5|+|13-8|+|13-11|=26~.