题目描述

哈尔滨以建筑物的夜间灯光而闻名。现在需要在尽量少的位置安装光源，使所有建筑物的两个竖直侧面都被完全照亮。

在二维平面中，第 $i$ 栋建筑由三个整数 $L_i,R_i,H_i$ 描述，它是一个边与坐标轴平行的矩形，两个对角点为 $(L_i,0)$ 与 $(R_i,H_i)$。所有建筑物两两不相交，甚至不会接触。

线段 $[(L_i,0),(L_i,H_i)]$ 与 $[(R_i,0),(R_i,H_i)]$ 称为这栋建筑的两个侧边，线段 $[(L_i,H_i),(R_i,H_i)]$ 称为它的顶边。

每个光源必须安装在某栋建筑物的顶边上，也允许安装在顶边端点上；同一栋建筑上可以安装任意多个光源。

设光源位于 $(x_1,y_1)$。若线段 $[(x_1,y_1),(x_2,y_2)]$ 的内部不经过任何建筑物的内部，则点 $(x_2,y_2)$ 会被该光源照亮。线段可以经过建筑物的边界或顶点，这不会造成遮挡。

若一条侧边上的每一点（包括两个端点）都至少被一个光源照亮，则称该侧边被完全照亮。

请计算使所有建筑物的两条侧边都被完全照亮所需的最少光源数。

输入格式

输入包含多组测试数据。

第一行一个整数 $T$，表示测试数据组数，其中 $1\le T\le10000$。

每组数据第一行一个整数 $N$，表示建筑物数量，其中 $1\le N\le1000$。

接下来 $N$ 行，每行三个整数 $L_i,R_i,H_i$，满足：

• $1\le L_i<R_i\le10000$；
• $1\le H_i\le10000$。

保证所有建筑物两两不相交且不接触。

并保证整个输入文件中所有测试数据的 $N^2$ 之和不超过 $10^6$。

输出格式

对每组测试数据输出一行一个整数，表示所需光源的最少数量。

样例

2
4
3 4 1
5 6 1
7 8 1
1 2 10
6
3 4 1
5 6 1
7 8 1
1 2 10
11 12 10
9 10 1

5
4