K. Kilometric Intersection
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

On the Pan-American Highway, two maintenance crews work on different road segments. Each segment is a closed interval on a line (in kilometers). To coordinate resources, we only need the length of the overlap between both segments.

Given two closed intervals $$$[a,b]$$$ and $$$[c,d]$$$ (with $$$a \le b$$$ and $$$c \le d$$$), print the length of their intersection on the real line. If they do not overlap (or only touch at a single point), the length must be $$$0$$$.

The length of a closed interval $$$[x,y]$$$ is defined as $$$y - x$$$.

Input

The first line contains an integer $$$T$$$ $$$(1 \le T \le 10^5)$$$, the number of test cases. Each of the next $$$T$$$ lines contains four integers $$$a,b,c,d$$$ $$$( -10^{18} \le a \le b \le 10^{18},\ -10^{18} \le c \le d \le 10^{18})$$$.

Output

For each test case, print a single integer: the intersection length.

Example
Input
6
3 7 1 5
0 0 0 0
-5 -1 2 8
1 10 3 6
-1 4 4 10
-10 -2 -7 0
Output
2
0
0
3
0
5
Note
  • If intervals only touch at an endpoint (e.g., $$$[0,1]$$$ and $$$[1,2]$$$), the intersection is $$$\{1\}$$$, whose length is $$$0$$$.
  • Use 64-bit integers to avoid overflow.