Scientists from the planet Zeelich have figured out a way to grow cabbages in space. They have constructed a huge 3-dimensional steel grid upon which they plant said cabbages. Each cabbage is attached to a corner in the grid, where 6 steel cables meet and is assigned Cartesian coordinates. A cosmic ant wants to crawl from cabbage X to cabbage Y along the cables that make the grid. The cosmic ant always chooses the shortest possible path along the grid lines while going from cabbage X to cabbage Y. This distance is called the cosmic distance between two cabbages. Given a collection of cabbages what is the maximum distance between any two of the cabbages? Input The first line of input gives the number of cases, N (0 < N < 21). N test cases follow. Each one starts with a line containing n (2 ≤ n ≤ 105). The next n lines will each give the 3-dimensional coordinates of a cosmic cabbage (integers in the range [−108,108]). Output For each test case, output one line containing ‘Case #x:’ followed by the largest cosmic distance between cabbages X and Y, out of all possible choices of X and Y. Sample Input 4 2 111 222 3 000 001 110 4 012 345 678 9 10 11 6 000 111 222 001 100 010 CABBAGE, n. A familiar kitchen-garden vegetable about as large and wise as a man’s head. Ambrose Bierce
2/2 Sample Output Case #1: 3 Case #2: 3 Case #3: 27 Case #4: 6