给定一个由 $$$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$$$。
示例
输入 #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
输出 #1
6 2 3
注意
在第一个测试用例中,对于每个 $$$k$$$ 可以实现 $$$a_k = 1$$$。为此,您可以使用以下操作:
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$$$。