← 返回题目列表

Codeforces · 2004/B

B. 门游戏

中文机器翻译题面 查看原题

有 $$$100$$$ 个房间排成一排,房间之间有 $$$99$$$ 个门;第 $$$i$$$ 门连接房间 $$$i$$$ 和 $$$i+1$$$。每扇门都可以上锁或解锁。最初,所有门均未上锁。

如果 $$$x$$$ 房间之间的所有门都未上锁,则可以从 $$$y$$$ 房间到达房间 $$$x$$$。

你知道:

- Alice 在 $$$[l, r]$$$ 段的某个房间里;
- Bob 在 $$$[L, R]$$$ 段的某个房间中;
- Alice 和 Bob 在不同的房间。

但是,您不知道他们所在的确切房间。

你不希望 Alice 和 Bob 能够联系到对方,所以你要锁上一些门来防止这种情况发生。为了让爱丽丝和鲍勃无法相遇,无论他们在给定段内的起始位置如何,您必须锁定的最少门数是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l < r \le 100$$$) - Alice 所在房间段的边界。

每个测试用例的第二行包含两个整数 $$$L$$$ 和 $$$R$$$ ($$$1 \le L < R \le 100$$$) — Bob 所在房间段的边界。

输出

对于每个测试用例,打印一个整数 - 您必须锁定的最小门数,以便 Alice 和 Bob 无法相遇,无论他们在给定段内的起始位置如何。

示例

输入 #1

4
1 2
3 4
2 5
2 5
3 7
6 7
4 5
2 8

输出 #1

1
3
2
3

注意

在第一个测试用例中,锁上房间 $$$2$$$ 和 $$$3$$$ 之间的门就足够了。

在第二个测试用例中,必须锁定以下门:$$$(2,3)$$$、$$$(3,4)$$$、$$$(4,5)$$$。

在第三个测试用例中,必须锁定以下门:$$$(5, 6)$$$ 和 $$$(6,7)$$$。