Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Building Boundaries

Limits 1s, 512 MB

Maarja wants to buy a rectangular piece of land and then construct three buildings on that land.

The boundaries of the buildings on the ground must have rectangular sizes $a_1 \times b_1$, $a_2 \times b_2$, and $a_3 \times b_3$. They can touch each other but they may not overlap. They can also be rotated as long as their sides are horizontal and vertical.

What is the minimum area of land Maarja has to buy?

Illustration of the two test scenarios in Sample Input 1 and their solutions. In the second scenario the $5 \times 1$ building has been rotated by $90$ degrees.

Input

The input consists of multiple test scenarios. The first line of input contains a single integer $t$ ($1 \le t \le 1000$), the number of scenarios. Then follow the $t$ scenarios. Each scenario consists of a single line, containing six integers $a_1$, $b_1$, $a_2$, $b_2$, $a_3$ and $b_3$ ($1 \le a_1,b_1,a_2,b_2,a_3,b_3 \le 10^9$).

Output

For each test scenario, output the minimum area of land such that Maarja can construct the three buildings.

Sample

InputOutput
2
2 3 2 2 1 1
2 4 5 1 2 3
12
21

This NCPC 2019 problem is licensed under the CC BY-SA 3.0 license.

You can find the original problem on the NCPC website.

    Discussion

    Statistics


    72% Solution Ratio

    kenechiEarliest, 2M ago

    c_utkarshFastest, 0.0s

    kenechiLightest, 131 kB

    user.004769Shortest, 842B

    Submit

    Login to submit