Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)


There are some key points in a plane that can absorb everything inside the plane. The problem is, “A gun is shooting the plane, what’s the probability for the bullets to be absorbed by each key point”?
The plane is a rectangle whose height and width equals 1. Points in plane can be defined as ( x, y ), 0 < x < 1 , 0 < y < 1. When shooting, the bullets follow the distribution below:

After a bullet falls into the plane, it will be absorbed by the nearest key point. You are given the position of every key point. Can you tell me the probability absorbed by them?


The first line contains a single integer T (T <= 100), the number of test cases.

For each case, the first line of each case is a integer n(n <= 100), n means the number of key points.
Following n lines, each line contains two number a and b, (a , b) means the position of a key point.


For each case, you should print one line begin with “Case #”(quotations for explanation only) followed by the case number. Then, output a float number with 6 digits after decimal point, representing the probability that absorbed by each key point.

Sample Input

2 1 0.5 0.5 2 0.25 0.5 0.75 0.5

Sample Output

Case #1: 1.000000 Case #2: 0.625000 0.375000
Recommend eps equal or smaller than 1e-11.




2012 Multi-University Training Contest 3