POLYU - POLYU

In the country of Giantarum, the king of Giantarum is AC. AC and his billions of hougong like to eat giantarum very much. The shape of giantarum is special! It could be regard as a triangle. There are N giantarums in the Cartesian coordinates, they may cover each other. AC wants to know the total area that is covered by giantarums.

Input

In the first line there is an integer T, indicates the number of test cases. (T ≤ 100)

In each case, the first line contains an integer N (N ≤ 100), indicates the number of the giantarum. The follow N line, every line contains six floating numbers x0, y0, x1, y2, x2, y2, indicates the coordinate of the three vertices of the giantarum. (all |xi| ≤ 104 and |yi| ≤ 104)

Output

For every test case, output one line. First output “Case idx: ”, here idx is the case number start from 1.Then output the area, rounded to 3 digits after the decimal point.

Example

Input:
2
1
0 0 1 0 1 1
2
0 0 1 0 1 1
0 0 0 1 1 1

Output:
Case 1: 0.500
Case 2: 1.000

Added by:aekdycoin
Date:2011-01-01
Time limit:0.806s-2.913s
Source limit:7000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:AekdyCoin

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.