Given a segment in a 3D space, identified by A(x1, y1, z1), B(x2, y2, z2) and another point P(x, y, z) your task is to find the minimum possible Euclidean distance between the point P and the segment AB.
Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.
Each case starts with a line containing nine integers x1, y1, z1, x2, y2, z2, x, y, z. The magnitude of any integer will not be greater than 100.
Output
For each case, print the case number and the distance. Errors less than 10-6 will be ignored.
Sample
| Sample Input | Sample Output |
|---|---|
2 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 | Case 1: 1 Case 2: 0.8164965809 |