Migrated from Lutece 1303 Happy Shape

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is a circle and rectangle on the plane. The center of the circle is ($cx$, $cy$), and its radius is $cr$.

The edges of the rectangle parallel to the x-axis or the y-axis, and its bottom left corner is ($x1$, $y1$) and top right corner is ($x2$, $y2$). What is the area of their intersection?

Input

The first line of input contains a number, indicating the number of test cases. ($T \leq 10000$)

For each case, there will be seven integers $cx, cy, cr, x1, y1, x2, y2$, their meaning is described above. ($-1000 \leq cx, cy, cr, x1, y1, x2, y2 \leq 1000, x1 \lt x2, y1 \lt y2$)

Output

For each case, output Case #i: first. ($i$ is the number of the test case, from $1$ to $T$).

Then output the area of the intersection of the circle and the rectangle, in decimals, round to $4$ decimal places.

Samples

3
0 0 2 -1 -1 1 1
0 0 1 0 0 2 2
1 1 1 100 100 200 200

Case #1: 4.0000
Case #2: 0.7854
Case #3: 0.0000

Resources

The 14th UESTC Programming Contest Preliminary