A16383. Satisfying Constraints

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.

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).

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

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$ .