Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

B. Farmer
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

John is a successful farmer and he would like to expand his business. For this reason he is going to buy a new plot of land to grow even more crops (and earn even more money). Currently there are T (0 ≤ T ≤ 1000) plots on sale and John wants to find the best deal. He considers deal the best if the price per area unit is the lowest. Can you help him by coding a solution that computes price per area unit?

Input

First line contains the number of plots T (0 ≤ T ≤ 1000). Each plot defined is as a quadrilateral by 4 integer points on the 2D plane (in clockwise or counterclockwise order), meaning there are 8 integers (32-bit) in total which describe geometry and location of the plot. Last number on the line represents the price of plot.

Output

For each plot output a line “Case #tc: x”, where tc is plot’s sequence number (starting from 1) and x is price per unit for the tc-th plot rounded to two decimal places.

Examples
Input
1
0 0 0 10 10 10 10 0 100
Output
Case #1: 1.00