Ramsés II foi o mais prestigioso dos faraós egípcios. Reinou entre 1279 a.C. e 1213 a.C. Construiu vários templos, inclusive os famosos templos de Núbia. O mais famoso é um esculpido na rocha, em Abu Simpel, perto da segunda catarata do Nilo, onde o próprio faraó é reproduzido. Com Nefertari e outras esposas teve provavelmente mais de 6 filhos, com quem gostava muito de brincar de um jogo que chamava de “pirâmide mais alta”. O jogo consistia do seguinte. As crianças recebiam pequenos paralelepípedos de diferentes dimensões (que podiam ser rotacionados), e deveriam com estes cubos construir a pirâmide mais alta que conseguissem. Para construí-la não podiam colocar um paralelepípedo maior sobre um menor, ou seja, se o bloco A está sobre o bloco B, tanto a largura como a profundidade de A devem ser menores ou iguais que as de B.
Amen-hotep, primogênito de Ramsés, era muito bom no jogo, e muitas vezes conseguia construir pirâmides muito mais altas que o pai conseguia. Então, Ramsés decidiu chamar o grande matemático da corte, Narmer, para encontrar para cada conjunto de paralelepípedos a maior pirâmide possível, isto é, a pirâmide com a maior altura possível.

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.
A primeira linha de cada instância contém um inteiros N, onde 1 ≤ N ≤ 15, indicando o número de blocos. Cada uma das N linhas seguintes possui três inteiros X, Y e Z que indicam as medidas do bloco.

Saída

Para cada instância imprima uma linha contendo a altura da maior pirâmide possível.

Exemplo

Entrada:
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

Saída:
150
33
110