Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Temporarily unavailable

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarp lives on the coordinate axis $$$Ox$$$ and travels from the point $$$x=a$$$ to $$$x=b$$$. It moves uniformly rectilinearly at a speed of one unit of distance per minute.

On the axis $$$Ox$$$ at the point $$$x=c$$$ the base station of the mobile operator is placed. It is known that the radius of its coverage is $$$r$$$. Thus, if Polycarp is at a distance less than or equal to $$$r$$$ from the point $$$x=c$$$, then he is in the network coverage area, otherwise — no. The base station can be located both on the route of Polycarp and outside it.

Print the time in minutes during which Polycarp will not be in the coverage area of the network, with a rectilinear uniform movement from $$$x=a$$$ to $$$x=b$$$. His speed — one unit of distance per minute.

Input

The first line contains a positive integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. In the following lines are written $$$t$$$ test cases.

The description of each test case is one line, which contains four integers $$$a$$$, $$$b$$$, $$$c$$$ and $$$r$$$ ($$$-10^8 \le a,b,c \le 10^8$$$, $$$0 \le r \le 10^8$$$) — the coordinates of the starting and ending points of the path, the base station, and its coverage radius, respectively.

Any of the numbers $$$a$$$, $$$b$$$ and $$$c$$$ can be equal (either any pair or all three numbers). The base station can be located both on the route of Polycarp and outside it.

Output

Print $$$t$$$ numbers — answers to given test cases in the order they are written in the test. Each answer is an integer — the number of minutes during which Polycarp will be unavailable during his movement.

Example

Input

9 1 10 7 1 3 3 3 0 8 2 10 4 8 2 10 100 -10 20 -17 2 -3 2 2 0 -3 1 2 0 2 3 2 3 -1 3 -2 2

Output

7 0 4 0 30 5 4 0 3

Note

The following picture illustrates the first test case.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/20/2020 15:18:47 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|