I don't have any idea to solve this problem LightOJ- 1130 — Intersection between Circle and Rectangle. Problem Link

This problem states that-

1130 — Intersection between Circle and Rectangle

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 common 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 Input

3

1 1 10

2 2 5 5

1 1 10

20 20 30 30

1 1 5

0 1 8 8

Sample Output

Case 1: 9

Case 2: 0

Case 3: 24.6014178376

Please give me some solution idea, hits or resource from which I can learn this kinds of stuffs. Thanks in advance.