4.1 The Great Library Quiet Zone 📖
The Great Library has 100 study rooms arranged in a row, numbered from 1 to 100. Between each pair of adjacent rooms is a soundproof door. Initially, all doors are open.
Two study groups, Team Alpha and Team Beta, need to use the library. Sound can travel between rooms if all doors between them are open.
Team Alpha will occupy a range of rooms [a, b], and Team Beta will occupy a range of rooms [x, y].
As the librarian, your task is to close the minimum number of doors to ensure that no sound can travel between the two teams, regardless of which specific rooms they choose within their assigned ranges.
Constraints
Input Constraints:
The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of scenarios to consider.
For each scenario:
The first line contains two integers a and b (1 ≤ a < b ≤ 100) — the range of rooms Team Alpha might use.
The second line contains two integers x and y (1 ≤ x < y ≤ 100) — the range of rooms Team Beta might use.
Input Format
The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of scenarios to consider.
For each scenario:
The first line contains two integers a and b (1 ≤ a < b ≤ 100) — the range of rooms Team Alpha might use.
The second line contains two integers x and y (1 ≤ x < y ≤ 100) — the range of rooms Team Beta might use.
Output Format
For each scenario, print a single integer — the minimum number of doors you need to close to ensure sound isolation between the teams.
Example 1
Input:
4
1 2
3 4
2 5
2 5
3 7
6 7
4 5
2 8
Output:
1
3
2
3
Explanation:
Scenario 1: Closing the door between rooms 2 and 3 is sufficient. Scenario 2: You need to close doors between rooms 2-3, 3-4, and 4-5. Scenario 3: Closing doors between rooms 5-6 and 6-7 ensures isolation. Scenario 4: Doors between rooms 3-4, 4-5, and 5-6 must be closed.
Log In to solve the Question