Hexagon

아래 그림과 같이 19개의 육각형 칸으로 이루어진 게임판이 있다. 이 게임판에는 세 가지 주요 방향이 있다. 위에서 아래로, 왼쪽 위에서 오른쪽 아래로, 오른쪽 위에서 왼쪽 아래로의 방향이다. 각 방향으로 게임판을 보면 칸의 개수가 각각 3, 4, 5, 4, 3개인 다섯 개의 줄로 나뉜다.

게임판은 육각형 조각들로 빈틈없이 덮어야 한다. 각 조각에는 세 방향에 대응하는 세 개의 수가 적혀 있다. 한 방향에는 서로 다른 세 개의 수만 사용되므로, 각 방향마다 하나씩 수를 고르는 모든 조합을 만들면 서로 다른 27개의 조각이 만들어진다. 조각은 회전할 수 없다.

덮인 게임판의 점수는 15개 줄 점수(세 방향 각각 5개 줄)의 합이다. 한 줄의 점수는 다음과 같이 정해진다. 그 줄에 놓인 모든 조각이 줄의 방향에 대해 같은 수를 가지면, 줄 점수는 그 수에 줄에 놓인 조각의 개수를 곱한 값이다. 그렇지 않으면 줄 점수는 0이다. 예를 들어 그림에서 가장 왼쪽 줄의 점수는 $3 \times 3 = 9$이고, 바로 오른쪽 줄의 점수는 $4 \times 11 = 44$이다.

27개의 조각 중 정확히 19개를 골라 게임판을 덮는다. 각 방향에 주어진 세 수에 대해, 얻을 수 있는 가장 높은 총점을 구하여라.

첫째 줄에 테스트 케이스의 개수 $n$이 주어진다. 각 테스트 케이스는 세 줄로 이루어지며, 각 줄에는 세 정수가 주어진다. 이 세 줄 중 $k$번째 줄은 $k$번째 방향에 사용되는 세 수를 나타내고, 이 수들로부터 27개의 조각이 만들어진다.

각 테스트 케이스마다 Test #k(여기서 $k$는 1부터 시작하는 테스트 케이스 번호)를 한 줄에 출력하고, 이어서 얻을 수 있는 가장 높은 점수를 한 줄에 출력한다. 연속한 테스트 케이스 사이에는 빈 줄을 하나 넣는다.