건물 경계

Maarja는 직사각형 토지를 사서 그 위에 건물 세 채를 지으려고 한다.

땅에 닿는 건물의 경계는 각각 a1 × b1, a2 × b2, a3 × b3 크기의 직사각형이어야 한다. 건물끼리 맞닿을 수는 있지만 겹쳐서는 안 된다. 또한 건물의 변이 가로와 세로 방향을 유지하는 한 회전시킬 수 있다.

Maarja가 사야 하는 토지의 최소 넓이는 얼마인가?

그림 B.1: 예제 입력 1의 두 시나리오와 그 해답을 나타낸 그림. 두 번째 시나리오에서는 5 × 1 건물을 90도 회전시켰다.

입력은 여러 개의 테스트 시나리오로 이루어진다. 첫째 줄에는 시나리오의 수 t (1 ≤ t ≤ 1000)가 주어진다. 이어서 t개의 시나리오가 주어진다. 각 시나리오는 한 줄로 이루어지며, 여섯 개의 정수 a1, b1, a2, b2, a3, b3 (1 ≤ a1, b1, a2, b2, a3, b3 ≤ 109)가 주어진다.

각 테스트 시나리오마다 Maarja가 건물 세 채를 지을 수 있는 토지의 최소 넓이를 출력한다.