T - Torta

Klára, veľká fanúšička 3D tlače, sa bude v sobotu vydávať. Kolegovia sa rozhodli vytvoriť špeciálnu tortu vytvorenú z kvádrov, ktoré boli vytlačené na 3D tlačiarni (tých majú veľa rôznych rozmerov, vznikli ako odpad počas rôznych testov). Tortu chcú hranatú pyramídového tvaru, takže kvádre budú na seba ukaladať vždy hranami rovnobežne, pričom vždy sa obidve strany podstavy musia zmenšiť. Jednotlivé kvádre môžu teda otáčať o 90 stupňov. Z každého rozmeru majú dostatočné množstvo kvádrov.

Úloha

Pre dané rozmery kvádrov určte akú najvyššiu tortu môžu kolegovia Kláre postaviť.

Vstup

V prvom riadku súboru sa nachádza počet typov kvádrov 1 ≤ T ≤ 700. Nasleduje T riadkov obsahujúcich rozmery kvádrov - 3 celé čísla 1 ≤ x, y, z ≤ 1.000 .

Výstup

Výstupom programu je jeden riadok, obsahujúci maximálnu výšku torty.

Príklad

Vstup:

3
1 2 3
4 5 6
5 6 7

Výstup:

22