URI Online Judge | 1450

Ramesses' Games

By Wanderley Guimarães, IME-USP Brazil
Timelimit: 5

Ramesses II was the most prestigious of all egyptian pharaohs. He reigned between 1279 BC - 1213 BC, and built various temples, including the famous Nubian temples. The most famous one is a rock sculpture, in Abu Simpel, close to the second Nile waterfall, where the very same pharaoh is reproduced. With Nefertari and other wives he probably had more than 6 childs, with whom he liked to play a game called "highest pyramid". The game was played as follows: the kids received small parallelepipeds of different dimensions (which could be rotated), and with those cubes they had to build the highest pyramid they could. To build it they couldn't place a block on top of a smaller one, that is, if block A is on top of the block B, both the width and depth of A should be smaller than those of B.

Amenhotep, his first-born son, was very good on this game, and could build pyramids that are much taller than his father's. So Ramesses decided to call the great mathematic of the court, Narmer, to find the highest pyramid possible to build for each set of parallelepipeds, that is, the highest pyramid possible to build.

Input

The input is composed of several test cases. The first line of the input contains an integer T indicating the number of test cases.

The first line of each instance contains an integer N, where 1 ≤ N ≤ 15, indicating the number of blocks. Each one of the N following lines will have three integers X, Y and Z that indicates the measurements of the block.

Output

For each instance print a line containing the height of the highest pyramid possible.

Sample Input Sample Output

3
5
10 10 10
50 50 50
40 40 40
20 20 20
30 30 30
2
20 20 20
30 33 10
2
100 10 10
100 12 8

150
33
110