Light it up

4.2

18 votes
Hard
Problem

There are N buildings placed on the line Y = 0. Each building can be considered as rectangle described by 3 integers Li, Ri, Hi with corners (Li; 0); (Ri; 0), (Li; Hi), (Ri; Hi) .

You can place any number of lights on the roof of any building at any point (i.e. at any point of any segment (Li; Hi) - (Ri; Hi) ). Your goal is to make all the side walls completely illuminated.

The point is considered as illuminated by some light source if the segment connecting the light source and the point contains no internal points of the buildings (but it can contain edge points).

What is the minimum number of lights you have to place to achieve your goal?

Input

The first line contains one integer T denoting the number of test cases.

Each of the following T test cases starts with the line containing one integer N - the number of building. The followng N lines contain 3 integers Li, Ri, Hi each.

It's guaranteed that buildings don't intersect or touch each other.

Output

For each test case output one integer on a separate line - the answer for this test.

Constraints

  • 1 <= N <= 1000
  • sum of squared values of N over all test cases doesn't exceed 1 000 000 in each test file.
  • 0 < Li, Ri, Hi <= 10 000
  • Li < Ri
Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?