Alex 正在解决问题。他对整数 $$$k$$$ 的大小有 $$$n$$$ 限制。约束分为三种类型:
1. $$$k$$$ 必须大于或等于某个整数 $$$x$$$;
2. $$$k$$$ 必须小于或等于某个整数 $$$x$$$;
3. $$$k$$$ 必须不等于某个整数 $$$x$$$。
帮助 Alex 找到满足所有 $$$n$$$ 约束的整数 $$$k$$$ 的数量。保证答案是有限的(存在至少一个 $$$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)$$$ 都是不同的)。
输出
对于每个测试用例,输出一个整数 - 满足所有 $$$n$$$ 约束的整数 $$$k$$$ 的数量。
示例
输入 #1
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
输出 #1
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$$$。