Two men are moving concurrently, one man is moving from A to B and other man is moving from C to D. Initially the first man is at A, and the second man is at C. They maintain constant velocities such that when the first man reaches B, at the same time the second man reaches D. You can assume that A, B, C and D are 2D Cartesian co-ordinates. You have to find the minimum Euclidean distance between them along their path.
Input
Input starts with an integer T (≤ 1000),denoting the number of test cases.
Each case will contain eight integers: Ax, Ay, Bx, By, Cx, Cy, Dx, Dy. All the co-ordinates are between 0 and 100. (Ax, Ay) denotes A. (Bx, By) denotes B and soon.
Output
For each case, print the case number and the minimum distance between them along their path. Errors less than 10-6 will be ignored.
Sample
| Sample Input | Sample Output |
|---|---|
3 0 0 5 0 5 5 5 0 0 0 5 5 10 10 6 6 0 0 5 0 10 1 1 1 | Case 1: 0 Case 2: 1.4142135624 Case 3: 1 |