Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Ant Query

By Tanmoy_Datta · Limits 1s, 512 MB

Scientists from the planet Krypton have figured out a way to grow artificial sugar in space. They have constructed a huge 3-dimensional steel grid upon which they will produce artificial sugar. Each sugar stock will be attached to a point on the grid. A cosmic ant wants to crawl from stock X to stock Y along the grid line.

The cosmic ant always chooses the shortest possible path along the grid lines while going from stock X to stock Y. The ant has an Energy capacity, and he loses 1 unit energy in walking 1 unit of distance. He can not walk further with 0 energy. Now, the scientists want to perform a test run on the grid. For that, they have to perform N operations. In each operation, they will produce a new sugar stock on the grid. Then they will ask you to find out the minimum required energy capacity for the ant such that tthe ant can visit any sugar stock from any other sugar stock.

Input

The first line of input gives the number of cases, T (1 ≤ T ≤ 5 ). T test cases follow. Each one starts with a line containing the number of operations N (1 ≤ N ≤ 5×104). The next N lines will each give the 3-dimensional coordinates of a sugar stock (integers in the range [−108, 108]).

Output

For each test case, output test case number and N lines containing the answer for each query.

Sample

InputOutput
3
3
1 5 4
3 0 2
5 2 1
4
4 5 0
4 5 4
2 0 4
1 5 2
1
1 2 3
Case #1:
0
9
10
Case #2:
0
4
11
11
Case #3:
0

Discussion

Statistics


68% Solution Ratio

EgorKulikovEarliest, Mar '20

EgorKulikovFastest, 0.1s

shefinLightest, 2.6 MB

serotoninShortest, 900B

Submit

Login to submit

Editorial

This problem ask you to find maximum Manhattan distance between any two available points on a 3d gri...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.