URI Online Judge | 1126

Star War

Maratona de Programação da SBC Brazil

Timelimit: 2

A long time ago, in a galaxy far, far away, there was an empire that dominated all others. A rebel alliance, unhappy with this situation, decided to fight these forces, with the objective of restoring democracy and peace for all nations.

Captain Cael, one of the rebel commanders, is sailing through space with his space cruiser, when he suddenly detects the presence of a ship of the Empire (according to the aesthetic standards of the time, all ships are tetrahedra). After a moment of surprise, Cael realizes he is in firing range and may place a cannon at any point of his ship.

As the power of his gun is fixed, Cael wants to position the cannon so that the distance traveled by the energy beam to the Empire\'s ship is minimal, to maximize the damage. Therefore, he asked that you, sub-master Cin Talig, compute the shortest distance between the rebel spacecraft and the spacecraft of the Empire.

Input

The input contains several test cases. The first line of the input contains an integer T, indicating the number of test cases. Each of the T test cases consists of eight lines, each line describing the coordinate of a vertex of a ship. The first four lines describe the vertices of the rebel spacecraft, the following four lines describe the vertices of the spacecraft of the Empire.

Each coordinate description is a line containing three integers X, Y, Z indicating the coordinate of the vertex in space (−103X ≤ 103, −103Y ≤ 103, −103Z ≤ 103). The four corners of each ship always define a tetrahedron of nonzero volume, and the two ships are always disjoint.

Output

For each test case in the input your program must print a line containing a single number, printed with precision of two decimal digits, indicating the minimum distance between the two spacecrafts. The distance between the two ships is always greater than zero.

Input Sample Output Sample

3
2 -1 -1
0 -1 -3
1 1 -4
1 1 -2
0 5 -1
2 5 1
1 3 2
1 3 0
1 0 -6
-5 0 -4
-2 6 -5
-2 2 -2
1 0 3
-5 0 5
-2 2 7
-2 -4 7
4 -4 -2
-2 -4 -4
1 4 -3
1 0 -4
-2 4 -1
4 4 1
1 -4 0
1 0 -1

2.83
6.03
1.90