#1600 SharksDinner

19  1 s   128 MB  

Description

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.

Input

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.

Output

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