12891289 SUSTech Online Judge
Problem 1289 --Palace

1289: Palace

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

Description

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.

Input

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.

Output

For each test case, print the maximum height.

Sample Input

1
3
2 3 5
4 3 4
3 3 3

Sample Output

9

HINT

Source

 

[Submit][Status]