Problem F: Palace

Problem F: Palace

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 852  Solved: 171
[Submit][Status][Web Board]


To celebrate the victory of the war, Pisces has decided to build a splendid palace. The craftsmen has brought back \(n\) kinds of cube materials from the dwarf kingdom. The length, width, and height of each material are \(a\), \(b\) and \(c\) respectively. To make the palace magnificent, the craftsmen have to stack these materials together. Material \(i\) can be stacked on material \(j\) if and only if \(a_i < a_j \bigcap b_i < b_j\), or \(a_i < b_j \bigcap b_i < a_j\). Pisces wants to know how high these materials can stack at most.


The first line contains an integer \(T\) \((1\leq T \leq 10)\), which denotes the number of test cases.

For each of the test cases, the first line contains an integer \(n\) \((1\leq n \leq 2*10^3)\), which represents the number of materials. Each of the next \(n\) lines contains \(3\) integers \(a\), \(b\) and \(c\) \((1\leq a,b,c\leq 1000)\), which represents the size of a material.


For each test case, print the maximum height.

Sample Input

2 3 5
4 3 4
3 3 3

Sample Output