4.1 The Great Library Quiet Zone ðŸ“–

Score: 10pts

Time Limit: 5.00 sec

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.

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.

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.

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.

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.