H. Rigged Matchmaking
time limit per test
2 s
memory limit per test
512 megabytes
input
standard input
output
standard output

The World Table Tennis Championship is approaching! This year, a serious competition is expected between two countries: Monland and Berland. Each country is represented by its national team.

Thanks to his high abilities (not only in tennis), Monocarp has made it to the Monland team. By studying and analyzing the previous performances of all team members, Monocarp was able to determine their skills. It turned out that Monland is represented by $$$(r_M - l_M + 1)$$$ athletes with skills $$$l_M$$$, $$$l_M + 1$$$, $$$l_M + 2$$$, and so on, up to $$$r_M$$$ inclusive. Similarly, Berland is represented by athletes with skills $$$l_B$$$, $$$l_B + 1$$$, ..., $$$r_B$$$. Unfortunately for Monocarp, he turned out to be that athlete with skill $$$l_M$$$.

The table tennis championship is organized in a very complicated way, but it will begin with a qualifying round. This round consists of a series of two-on-two games: two representatives from Monland play against two athletes from Berland.

To Monocarp's great joy, the selection of athletes for the games is done by an electronic system. Since Monocarp is also a fairly strong programmer, he managed (not without effort) to hack this system and can now control the team compositions for the games.

His plan is to manipulate the matches he participates in and ensure his victories in them. Monocarp believes that he and his partner will be able to defeat an opposing team if the total skill of his team is higher than or equal to the total skill of their two opponents.

However, Monocarp decided that it would be safer if none of the athletes he plays with or against are repeated. Thus, Monocarp wants to arrange the games so that no athlete from Berland plays against Monocarp more than once, and no athlete from Monland plays with him more than once.

Help Monocarp determine the maximum number of winning games he can arrange in this way.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases.

The first line of each test case contains two integers $$$l_M$$$ and $$$r_M$$$ ($$$1 \le l_M \lt r_M \le 10^9$$$) — the skill levels of Monland's team. Monocarp is the one who has skill $$$l_M$$$.

The second line of each test case contains two integers $$$l_B$$$ and $$$r_B$$$ ($$$1 \le l_B \lt r_B \le 10^9$$$) — the skill levels of Berland's team.

Output

For each test case, print one integer — the maximum number of wins Monocarp can achieve.

Example
Input
3
10 13
11 15
2000 3000
1 2000
42 200
1 400
Output
1
1000
96
Note

In the first test case, even if Monocarp (skill $$$10$$$) joined forces with the strongest athlete in his team (the one with skill $$$13$$$), they can only win against a team consisting of the two weakest athletes of the Berland's team (athletes with skills $$$11$$$ and $$$12$$$), since $$$10 + 13 \ge 11 + 12$$$.

In the second test case, it doesn't matter who Monocarp will play with and against, since any Monocarp's team will have total skill higher than $$$4000$$$ while any Berland team skill is lower than $$$4000$$$.