19 1 s 128 MB

Some sharks are having dinner and they are eating each other. For every shark we know its size, speed and intelligence (measured in positive integers). Shark A can eat shark B if and only if A's size, speed and intelligence are all greater than or equal to B's. Due to digestive restrictions, each shark can eat at most two other sharks.

The first line of the input gives the number of test cases, T. T test cases follow, each test case consists several lines. First line of each test case, given N, number of sharks. (1 <= N <= 50). And following N lines, gives each shark’s size, speed, intelligence. Shark’s size, speed, intelligence will be between 1 and 2,000,000,000, inclusive.

For each test case, output the minimum number of sharks that will survive.

## Sample Input | ## Sample Output |
---|---|

4 3 1 2 1 4 3 5 3 1 2 5 4 5 5 10 10 8 5 7 10 8 7 7 8 10 3 5 1 4 2 2 3 4 3 2 1 4 1 3 100 100 100 4 4 3 8 4 3 8 4 3 8 4 3 8 | 1 2 3 1 |