C :: Game of Heroes

Time Limit: 3 Seconds    Memory Limit: 65536 KB

Marcus and Cirius were playing a game, where one of them had to choose a hexagon and the other one had to place it in a board like what shown in the picture. During the game every player bluffed about how pro they were at the game so Marcus decides to challenge Cirius in the following game: Marcus gives three sets of numbers to Cirius and then, he has to put them in the tiles each number for a certain direction (directions are: top to bottom, top-left to bottom-right, and top-right to bottom-left) as he wishes, and then put that tiles on the board to maximize his score.

The score is calculated in a fashion that for each of the primary directions, if the numbers are equal for all tiles, the sum of numbers chosen for every row is known to be the score of row. For instance, in the given figure, first column on left adds up to 9 (3 tiles each counting as 3). However, if chosen numbers do not match for a row, score for that row is zero. Scores for all rows are accumulated to shape the final score of game.

Input

The first line of the input file contains an integer n which indicates the number of test cases. Each test case consists of three lines containing three integers each. Each of these three line contains the numbers for a single primary direction. From these numbers the set of tiles is generated.

Output

For each test case output a line containing the number of the case ('Test #1', 'Test #2', etc.), followed by a line containing the highest possible score for the given numbers. Add a blank line after each test case.

Sample Input

1
9 4 3
8 5 2
7 6 1

Sample Output

Test #1
308

Submit