1366B · Shuffle

Problem: You are given an array consisting of $n$ integers $a_1$, $a_2$, ..., $a_n$. Initially $a_x = 1$, all other elements are equal to $0$.

You have to perform $m$ operations. During the $i$-th operation, you choose two indices $c$ and $d$ such that $l_i \le c, d \le r_i$, and swap $a_c$ and $a_d$.

Calculate the number of indices $k$ such that it is possible to choose the operations so that $a_k = 1$ in the end.

Input Format: The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Then the description of $t$ testcases follow.

The first line of each test case contains three integers $n$, $x$ and $m$ ($1 \le n \le 10^9$; $1 \le m \le 100$; $1 \le x \le n$).

Each of next $m$ lines contains the descriptions of the operations; the $i$-th line contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$).

Output Format: For each test case print one integer — the number of indices $k$ such that it is possible to choose the operations so that $a_k = 1$ in the end.

Note: In the first test case, it is possible to achieve $a_k = 1$ for every $k$. To do so, you may use the following operations:

1. swap $a_k$ and $a_4$;
2. swap $a_2$ and $a_2$;
3. swap $a_5$ and $a_5$.

In the second test case, only $k = 1$ and $k = 2$ are possible answers. To achieve $a_1 = 1$, you have to swap $a_1$ and $a_1$ during the second operation. To achieve $a_2 = 1$, you have to swap $a_1$ and $a_2$ during the second operation.