Welcome to ZOJ
65 - ZOJ Monthly, May 2008 - 1001
Another Horizontally Visible Segments

Time Limit: 2 Seconds      Memory Limit: 65536 KB

There are a number of disjoint vertical line segments in the plane. We say that two vertical line segments are horizontally visible if they can be connected by a horizontal line segment. A clique is a set of vertical line segments, in which any two segments in the set are horizontally visible. Your job is to find the largest clique.

Read the description of a set of vertical segments, you are to compute the largest clique of the segments and output the number of the segments in the largest clique.


The first line of the input contains exactly one positive integer T equal to the number of data sets. T data sets follow.

The first line of each data set contains exactly one integer N (1 <= N <= 4000) equal to the number of vertical line segments.

Each of the following N lines consists of exactly 3 non-negative integers separated by single spaces:

Xi , Yi1 , Yi2 - its x-coordinate, y-coordinate of the beginning of a segment and y-coordinate of its end. The coordinates satisfy 0 <= Yi1 < Yi2 <= 10000. The segments are disjoint.


The output should consist of exactly N lines, one line for each data set. Each line should contain exactly one integer that is the number of the segments in the largest clique.

Sample Input

1 0 1
2 1 2
3 0 3

Sample Output


Author: PENG, Peng

Submit    Status