Problem F: Palace

## Problem F: 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

[Submit][Status]