Hai người đàn ông đang di chuyển đồng thời, một người đang di chuyển từ A đến B và người kia đang di chuyển từ C đến D. Ban đầu người thứ nhất ở A, và người thứ hai ở C. Họ duy trì vận tốc không đổi sao cho khi người thứ nhất đến B, thì cùng lúc đó người thứ hai đến D. Bạn có thể cho rằng A, B, C và D là tọa độ Descartes 2D. Bạn phải tìm khoảng cách Euclidean nhỏ nhất giữa hai người đàn ông khi di chuyển trên đường đi.

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên dương T T (≤ 1000) – số testcase;
• T dòng tiếp theo, mỗi dòng chứa 8 số nguyên dương Ax, Ay, Bx, By, Cx, Cy, Dx, Dy. Tất cả các tọa độ đều nằm trong khoảng từ 0 đến 100. Trong đó (Ax, Ay) biểu diễn tọa độ điểm A, (Bx, By) biểu diễn tọa độ điểm B, (Cx, Cy) biểu diễn tọa độ điểm C và (Dx, Dy) biểu diễn tọa độ điểm D.

Dữ liệu ra:

*Đối với mỗi testcase, in ra khoảng cách tối thiểu giữa hai người đàn ông khi di chuyển trên đường đi của họ.

Ví dụ:

Dữ liệu vào:

2
21 69 34 58 47 80 67 63
28 96 7 0 64 13 82 77

Dữ liệu ra:

Case 1: 28.2311884270
Case 2: 54.6317196562