Problem A
Cosmic Cabbages
Input: Standard Input

Output: Standard Output

Ambrose Bierce

Scientistsfrom the planet Zeelich have figured out a way togrow cabbages in space. They have constructed a huge 3-dimensional steel gridupon which they plant said cabbages. Each cabbage is attached to a corner inthe grid, where 6 steel cables meet and is assigned Cartesian coordinates. Acosmic ant wants to crawl from cabbage X to cabbage Y along the cables thatmake the grid. The cosmic ant always chooses the shortest possible path alongthe grid lines while going from cabbage X to cabbage Y. This distance is calledthe cosmic distance between two cabbages. Given a collection of cabbages whatis the maximum distance between any two of the cabbages?

Input

The first line of input gives thenumber of cases, N (0<N<21). N test cases follow. Each onestarts with a line containing n (2<=n<=10⁵).The next n lines will each give the 3-dimensional coordinates of acosmic cabbage (integers in the range [-10⁸, 10⁸]).

Output

For each testcase, output one line containing "Case #x:" followed by thelargest cosmic distance between cabbages X and Y, out of all possible choicesof X and Y.

Sample Input                               Output forSample Input

0 1 0

Problem setter: Igor Naverniouk,EPS

Special Thanks: Shahriar Manzoor, EPS

I likedthis problem so much that I said to myself “If I were the problem setter ofthis problem?”

-ShahriarManzoor