#CF2004B. 门与游戏

门与游戏

B. 门与游戏
时间限制:每测试点 22
内存限制:256256 兆字节

100100 个房间排成一排,它们之间有 9999 道门;第 ii 道门连接房间 iii+1i+1。每道门可以是锁上的或者未锁的。初始时,所有门都是未锁的。

我们称房间 xx 可以从房间 yy 到达,如果它们之间所有的门都是未锁的。

已知:

  • 爱丽丝位于区间 [l,r][l, r] 中的某个房间;
  • 鲍勃位于区间 [L,R][L, R] 中的某个房间;
  • 爱丽丝和鲍勃在不同的房间。

但你不知道他们具体在哪个房间。

你不想让爱丽丝和鲍勃能够互相到达,因此你准备锁上一些门来阻止这种情况。问:最少需要锁上多少道门,使得无论他们在给定区间内的起始位置如何,爱丽丝和鲍勃都无法相遇?


输入格式
第一行包含一个整数 tt1t1041 \le t \le 10^4)——测试用例的数量。

每个测试用例的第一行包含两个整数 llrr1l<r1001 \le l < r \le 100)——爱丽丝所在房间的区间范围。

每个测试用例的第二行包含两个整数 LLRR1L<R1001 \le L < R \le 100)——鲍勃所在房间的区间范围。


输出格式
对于每个测试用例,输出一个整数——最少需要锁上的门数量,使得无论他们在给定区间内的起始位置如何,他们都不能相遇。


样例输入

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

样例输出

1
3
2
3

样例解释

  • 第一个测试用例:只需锁上房间 2233 之间的门。
  • 第二个测试用例:必须锁上门 (2,3)(2,3)(3,4)(3,4)(4,5)(4,5)
  • 第三个测试用例:必须锁上门 (5,6)(5,6)(6,7)(6,7)