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 {W_i (width), H_i (height), D_i (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 ≤ 10³)

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

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}.