数轴上给出了 $$$n$$$ 彩色线段。每个部分的颜色为红色或蓝色。第 $$$i$$$ 段可以由元组 $$$(c_i, l_i, r_i)$$$ 表示。该线段包含 $$$[l_i, r_i]$$$(含)范围内的所有点,其颜色由 $$$c_i$$$ 表示:
- 如果$$$c_i = 0$$$,则它是红色段;
- 如果 $$$c_i = 1$$$,则它是蓝色段。
如果两个不同颜色的线段至少共享一个公共点,我们就说它们是相连的。如果两个线段直接连接或通过一系列直接连接的线段连接,则它们属于同一组。求线段组的数量。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 段数。
接下来的 $$$n$$$ 行包含三个整数 $$$c_i, l_i, r_i$$$ ($$$0 \leq c_i \leq 1, 0 \leq l_i \leq r_i \leq 10^9$$$),描述第 $$$i$$$ 段。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印一个整数 $$$k$$$,即段组的数量。
示例
输入 #1
2 5 0 0 5 1 2 12 0 4 7 1 9 16 0 13 19 3 1 0 1 1 1 2 0 3 4
输出 #1
2 3
注意
在第一个示例中,有 $$$5$$$ 段。线段 $$$1$$$ 和 $$$2$$$ 是相连的,因为它们具有不同的颜色并且共享一个点。此外,线段 $$$2$$$ 和 $$$3$$$ 是相连的,线段 $$$4$$$ 和 $$$5$$$ 也是相连的。因此,有两组:一组包含段 $$$\{1, 2, 3\}$$$,另一组包含段 $$$\{4, 5\}$$$。