Given the co-ordinates of a circle and the lower left and upper right coordinate of an axis parallel rectangle, you have to find their interseciton area. In the picture, the shaded area is their common area.
Input
Input starts with an integer T (≤ 4000), denoting the number of test cases.
Each case contains two lines, first line contains three integers x, y, r where (x, y) denotes the center of the circle and r denotes the radius.
The next line contains four integers x1, y1, x2, y2 (x1<x2, y1<y2). All the integers are non-negative and not greater than 200.
Output
For each case, print the case number their common area. Errors less than 10-6 will be ignored.
Sample
| Sample Input | Sample Output |
|---|---|
3 1 1 10 2 2 5 5 1 1 10 20 20 30 30 1 1 5 0 1 8 8 | Case 1: 9 Case 2: 0 Case 3: 24.6014178376 |