B. Перемешивание
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив, состоящий из $$$n$$$ чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$. Изначально $$$a_x = 1$$$, а остальные элементы равны $$$0$$$.

Вы выполняете $$$m$$$ операций. Во время $$$i$$$-й операции вы выбираете два индекса $$$c$$$ и $$$d$$$ таких, что $$$l_i \le c, d \le r_i$$$, и меняете местами $$$a_c$$$ и $$$a_d$$$.

Посчитайте количество индексов $$$k$$$ таких, что существуют возможность выбрать операции так, что в конце $$$a_k = 1$$$.

Входные данные

Первая строка содержит число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Затем следует описание каждого из $$$t$$$ наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$x$$$ и $$$m$$$ ($$$1 \le n \le 10^9$$$; $$$1 \le m \le 100$$$; $$$1 \le x \le n$$$).

Каждая из следующих $$$m$$$ строк содержит описание операций; а именно — в $$$i$$$-й строке содержится два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

Выходные данные

На каждый набор входных данных выведите одно число — количество индексов $$$k$$$ таких, что существуют возможность выбрать операции так, что в конце $$$a_k = 1$$$.

Пример
Входные данные
3
6 4 3
1 6
2 3
5 5
4 1 2
2 4
1 2
3 3 2
2 3
1 2
Выходные данные
6
2
3
Примечание

В первом наборе входных данных условие $$$a_k = 1$$$ выполняется для любого $$$k$$$. Для этого, можно выполнить следующие операции:

  1. поменять местами $$$a_k$$$ и $$$a_4$$$;
  2. поменять местами $$$a_2$$$ и $$$a_2$$$;
  3. поменять местами $$$a_5$$$ и $$$a_5$$$.

Во втором наборе входных данных подходят только индексы $$$k = 1$$$ и $$$k = 2$$$. Для выполнения $$$a_1 = 1$$$, нужно поменять местами $$$a_1$$$ и $$$a_1$$$ во второй операции. Для выполнения $$$a_2 = 1$$$, нужно поменять местами $$$a_1$$$ и $$$a_2$$$ во второй операции.