Doro is the chief commanding officer of two space stations, Mungi and Hanzi. To make both stations gorgeous, he has decided to change the color of both stations. He has rented the robot Bingo to do this job. Since everything in space is too costly, using Bingo is costly too. The cost of Bingo depends on the amount of time it works. In each second Bingo can either color 1 meter2 area or fly 1 meter. Bingo always flies in a straight line.
Every space station has some critical points. A station is created by covering all the critical points together with minimal surface area, just like a 3D convex hull. All the faces of each space station are triangular shaped. It is guaranteed that each space station has nonzero volume.
At first Bingo colors the whole surface area of first space station Mungi. Then it flies to second space station Hanzi in the shortest distance. After reaching there it colors the station Hanzi. Time to move within a space station is negligible.
Find required time (both coloring and flying) to color both of the space stations by Bingo. It is guaranteed that the shortest distance between the space stations is more than 1 meter and stations are always disjoint.
Input
The first line of the input contains an integer T (T ≤ 25), the number of test sets.
Each set of input contains the description of two space stations one by one. Description of each space station starts with line containing a single integer N (N ≤ 12) denotes the number of critical points of that station. Following N line contain three space separated integers X, Y and Z (−103 ≤ X, Y, Z ≤ 103) denoting three coordinates of each critical point.
Each input sets starts with a blank line.
Output
For each case, print the minimum time (in second) required to color both of the space stations in single line. Errors less than 10-4 will be ignored.
Sample
| Input | Output |
|---|---|
2 4 2 2 19 0 100 -5 0 100 -25 10 10 -10 4 -100 0 0 100 0 -1 0 -100 -3 0 -1 300 6 2 2 5 2 3 19 0 0 0 50 0 2 0 50 -5 0 0 51 5 15 16 -9 5 5 -88 0 0 -100 50 0 -100 0 50 -100 | 88463.8596821524 15174.2234459270 |
