GIFTARNG - Gift Arrangement

Duck's birthday is coming soon! Unfortunately, this year nobody will come to Duck's birthday party. To make himself feel better, he has decided to display all birthday gifts received last year, pretending many people celebrate with him this year.

There are N gifts received last year, each in a rectangular gift box with dimensions {Wi (width), Hi (height), Di (depth)}. Gift box is very colorful which makes people happy, so Duck will place all of them in a straight line without changing the order and without any gap between two adjacent boxes, while the total visible area is maximized. To achieve this goal, Duck can rotate each gift box in any direction but the box must stand upright on the ground. That is, it cannot be placed obliquely. Please help him figure out the largest visible area.

Input

The first line is the number of test cases T. (1 ≤ T ≤ 30)

For each test case, it starts with the number of gifts received last year N. (1 ≤ N ≤ 103)

Following N lines, each consisting of three integers Wi (width) Hi (height) Di (depth), representing the dimensions of the i gift box. (1 ≤ Wi, Hi, Di ≤ 105)

Output

Output the largest visible area.

Example

Input:
2
2
100 100 20
3 4 2
 
3
1 1 1
5 4 3
8 6 8
Output:
26032
330

Explanation

In case 1, one optimal strategy is to rotate the first box to {100, 20, 100} and the second box to {4, 2, 3}.
In case 2, no rotation for the first box and third box, and to rotate the second box to {5, 3, 4}.


Added by:him0727
Date:2018-07-26
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own problem

hide comments
2018-07-27 08:12:52
Good implementation problem!!

Last edit: 2018-07-27 08:45:57
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.