21764_IlluminationofBuildings

The city of Harbin is famous for the nighttime illumination of its buildings. Unfortunately, the economic crisis of the world has not left the welfare of the city undisturbed. An audit performed by the city council has revealed that lighting is the single largest expense in the budget of the city. Accordingly, it was decided to cut the costs for lightning as much as possible, but without sacrificing the quality of the illumination, as the council has no desire to damage the world fame of the city.

Let's consider a 2-dimensional model of the city where each building is described by three integers L, R, H and modeled as a rectangle with edges parallel to the coordinate axes and two opposing corners at the points (L, 0) and (R, H). It may be assumed that the rectangles in the model do not intersect and even do not touch each other. Line segments [(L, 0) , (L, H)] and [(R, 0) , (R, H)] are called the side edges and line segment [(L, H) , (R, H)] the top edge.

The city council plans to install a number of light sources to illuminate the buildings. Each light source is to be installed on a top edge of a building (possibly on an endpoint of the top edge). There may be any number of light sources on one building. It is known that a light source installed at (x₁, y₁) will illuminate all points (x₂, y₂) where the line segment [(x₁, y₁), (x₂, y₂)] does not contain any internal points of any buildings. It is allowed for the segment to contain any (even infinite) number of edge and corner points of buildings.

The gure above shows a light source and all points illuminated by it.

You are asked to install the minimal number of light sources to ensure that both sides of each building are completely illuminated. A side of a building is completely illuminated if for every point P on the side (including endpoints) there exists at least one light source L that illuminates the point P.

The input file contains several test cases. The first line of the file contains T (1 ≤ T ≤ 10000), the number of test cases. The line is followed by T blocks, each describing a test case.

The first line of a block contains N (1 ≤ N ≤ 1000), the number of buildings in the city. Each of the following N lines describes one building and contains three integers L, R and H (1 ≤ L < R ≤ 10000, 1 ≤ H ≤ 10000).

It may be assumed that the sum of squares of values of N over all test cases in an input file does not exceed 1000000.

The output file should contain one line for each test case given in the input file. Each line should contain a single integer, the minimal number of light sources required to illuminate both side edges of all the buildings in the city.

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