Sunlight Hours (Small)

A is about to get married and has enough money for a home, but picking one with enough sunlight is hard. The city is full of buildings, and many homes sit in another building's shadow for much of the day. Work out how many homes in the city meet A's requirement.

The sun rises at $(-R, 0)$ at 6 in the morning, travels a semicircular path of radius $R$ at a constant speed, and sets at $(R, 0)$ 12 hours later at 6 in the evening. The center of the semicircle is the origin $(0, 0)$ on the ground.

The vertical lines in the picture are buildings, and the blue region is the interval of time when the sun reaches the home at the very bottom of the middle building.

The city has $N$ buildings. Building $i$ is the vertical segment from $(X_i, 0)$ to $(X_i, Y_i)$ and has zero thickness. No two buildings stand at the same coordinate.

Every building holds infinitely many homes of the same form, and no two homes in one building sit at the same height. The homes are spread evenly along the height of the building from the ground to the top, and the number of homes per unit of height is the same in every building. The share of homes that satisfy a condition is therefore the total length of the heights that satisfy it, divided by the sum of all building heights $Y_1 + Y_2 + \cdots + Y_N$.

The home at height $h$ in building $i$ is the point $(X_i, h)$, where $0 \le h \le Y_i$. The sun reaches that home at a given moment when the segment joining the home and the sun is not blocked by another building. That is, for every building $j$ with $j \ne i$, if the segment crosses the line $x = X_j$, the crossing point must be higher than $Y_j$. The home's own building has zero thickness, so it never blocks the sun.

Find the share of homes that get at least $H$ hours of sun in a day.

The first line holds the number of test cases $T$.

Each test case is given in this form.

N R H
X1 Y1
...
XN YN

On the first line, $N$ is the number of buildings, $R$ is the radius of the semicircle the sun travels, and $H$ is the smallest number of sunlit hours A accepts. Each of the next $N$ lines holds the coordinate $X_i$ and the height $Y_i$ of one building. Coordinates are measured from the center of the semicircle.

Constraints

• $1 \le T \le 100$
• $1 \le N \le 5$
• $100 \le R \le 1000$
• $1 \le H \le 12$
• $Y_i > 0$
• $X_i^2 + Y_i^2 < R^2$
• The values $X_i$ are distinct within one test case.
• Every number in the input is an integer.

For each test case print one line in the form Case #x: y. Here $x$ is the test case number starting from 1, and $y$ is the share of homes that get at least $H$ hours of sun in a day. Print $y$ rounded to seven digits after the decimal point, with all seven digits shown.