311005: CF1920A. Satisfying Constraints

A. Satisfying Constraintstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Alex is solving a problem. He has $n$ constraints on what the integer $k$ can be. There are three types of constraints:

1. $k$ must be greater than or equal to some integer $x$;
2. $k$ must be less than or equal to some integer $x$;
3. $k$ must be not equal to some integer $x$.

Help Alex find the number of integers $k$ that satisfy all $n$ constraints. It is guaranteed that the answer is finite (there exists at least one constraint of type $1$ and at least one constraint of type $2$). Also, it is guaranteed that no two constraints are the exact same.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 500$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 100$) — the number of constraints.

The following $n$ lines describe the constraints. Each line contains two integers $a$ and $x$ ($a \in \{1,2,3\}, \, 1 \leq x \leq 10^9$). $a$ denotes the type of constraint. If $a=1$, $k$ must be greater than or equal to $x$. If $a=2$, $k$ must be less than or equal to $x$. If $a=3$, $k$ must be not equal to $x$.

It is guaranteed that there is a finite amount of integers satisfying all $n$ constraints (there exists at least one constraint of type $1$ and at least one constraint of type $2$). It is also guaranteed that no two constraints are the exact same (in other words, all pairs $(a, x)$ are distinct).

Output

For each test case, output a single integer — the number of integers $k$ that satisfy all $n$ constraints.

ExampleInput

6
4
1 3
2 10
3 1
3 5
2
1 5
2 4
10
3 6
3 7
1 2
1 7
3 100
3 44
2 100
2 98
1 3
3 99
6
1 5
2 10
1 9
2 2
3 2
3 9
5
1 1
2 2
3 1
3 2
3 3
6
1 10000
2 900000000
3 500000000
1 100000000
3 10000
3 900000001

Output

7
0
90
0
0
800000000

Note

In the first test case, $k \geq 3$ and $k \leq 10$. Furthermore, $k \neq 1$ and $k \neq 5$. The possible integers $k$ that satisfy the constraints are $3,4,6,7,8,9,10$. So the answer is $7$.

In the second test case, $k \ge 5$ and $k \le 4$, which is impossible. So the answer is $0$.

题目大意：
这个题目是关于整数k满足一系列约束条件的问题。有三种类型的约束条件：
1. k必须大于或等于某个整数x；
2. k必须小于或等于某个整数x；
3. k必须不等于某个整数x。

保证至少存在一个类型1的约束和一个类型2的约束，并且答案是有穷的（即存在至少一个满足所有约束的整数k）。同时保证没有两个相同的约束。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤500），表示测试用例的数量。
- 每个测试用例的第一行包含一个整数n（2≤n≤100），表示约束条件的数量。
- 接下来的n行，每行包含两个整数a和x（a∈{1,2,3}, 1≤x≤10^9）。a表示约束的类型。如果a=1，则k必须大于或等于x；如果a=2，则k必须小于或等于x；如果a=3，则k必须不等于x。
- 保证存在至少一个约束类型1和至少一个约束类型2，且所有约束条件对(即(a, x)对)都是唯一的。

输出：
- 对于每个测试用例，输出一个整数，表示满足所有n个约束的整数k的数量。

示例输入输出：
输入：
```
6
4
1 3
2 10
3 1
3 5
2
1 5
2 4
10
3 6
3 7
1 2
1 7
3 100
3 44
2 100
2 98
3 99
6
1 5
2 10
1 9
2 2
3 2
3 9
5
1 1
2 2
3 1
3 2
3 3
6
1 10000
2 900000000
3 500000000
1 100000000
3 10000
3 900000001
```
输出：
```
7
0
90
0
0
800000000
```题目大意： 这个题目是关于整数k满足一系列约束条件的问题。有三种类型的约束条件： 1. k必须大于或等于某个整数x； 2. k必须小于或等于某个整数x； 3. k必须不等于某个整数x。 保证至少存在一个类型1的约束和一个类型2的约束，并且答案是有穷的（即存在至少一个满足所有约束的整数k）。同时保证没有两个相同的约束。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤500），表示测试用例的数量。 - 每个测试用例的第一行包含一个整数n（2≤n≤100），表示约束条件的数量。 - 接下来的n行，每行包含两个整数a和x（a∈{1,2,3}, 1≤x≤10^9）。a表示约束的类型。如果a=1，则k必须大于或等于x；如果a=2，则k必须小于或等于x；如果a=3，则k必须不等于x。 - 保证存在至少一个约束类型1和至少一个约束类型2，且所有约束条件对(即(a, x)对)都是唯一的。 输出： - 对于每个测试用例，输出一个整数，表示满足所有n个约束的整数k的数量。 示例输入输出： 输入： ``` 6 4 1 3 2 10 3 1 3 5 2 1 5 2 4 10 3 6 3 7 1 2 1 7 3 100 3 44 2 100 2 98 3 99 6 1 5 2 10 1 9 2 2 3 2 3 9 5 1 1 2 2 3 1 3 2 3 3 6 1 10000 2 900000000 3 500000000 1 100000000 3 10000 3 900000001 ``` 输出： ``` 7 0 90 0 0 800000000 ```