A. Выполнение условий
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алекс решает задачу. У него есть $$$n$$$ ограничений на то, каким может быть целое число $$$k$$$. Существует три типа ограничений:

  1. $$$k$$$ должно быть больше или равно некоторому целому числу $$$x$$$;
  2. $$$k$$$ должно быть меньше или равно некоторому целому числу $$$x$$$;
  3. $$$k$$$ должно быть не равно некоторому целому числу $$$x$$$.

Помогите Алексу найти количество целых чисел $$$k$$$, которые удовлетворяют всем $$$n$$$ ограничениям. Гарантируется, что ответ конечен (существует хотя бы одно ограничение типа $$$1$$$ и хотя бы одно ограничение типа $$$2$$$). Также гарантируется, что ни одно из ограничений не совпадает в точности с другим.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 100$$$) — количество ограничений.

Следующие $$$n$$$ строк описывают ограничения. Каждая строка содержит два целых числа $$$a$$$ и $$$x$$$ ($$$a \in \{1,2,3\}, \, 1 \leq x \leq 10^9$$$). Число $$$a$$$ обозначает тип ограничения. Если $$$a=1$$$, то $$$k$$$ должно быть больше или равно $$$x$$$. Если $$$a=2$$$, то $$$k$$$ должно быть меньше или равно $$$x$$$. Если $$$a=3$$$, то $$$k$$$ должно быть не равно $$$x$$$.

Гарантируется, что существует конечное количество целых чисел, удовлетворяющих всем $$$n$$$ ограничениям (существует хотя бы одно ограничение типа $$$1$$$ и хотя бы одно ограничение типа $$$2$$$). Также гарантируется, что ни одно из ограничений не совпадает в точности с другим (другими словами, все пары $$$(a, x)$$$ различны).

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

Для каждого набора входных данных выведите одно целое число — количество целых чисел $$$k$$$, удовлетворяющих всем $$$n$$$ ограничениям.

Пример
Входные данные
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
Выходные данные
7
0
90
0
0
800000000
Примечание

В первом наборе входных данных $$$k \geq 3$$$ и $$$k \leq 10$$$. Кроме того, $$$k \neq 1$$$ и $$$k \neq 5$$$. Возможные целые числа $$$k$$$, удовлетворяющие ограничениям: $$$3,4,6,7,8,9,10$$$. Поэтому ответ равен $$$7$$$.

Во втором наборе входных данных $$$k \ge 5$$$ и $$$k \le 4$$$, что невозможно. Поэтому ответ равен $$$0$$$.