Migrated from Lutece 558 Darwin

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

Darwin likes to write poetry about geometry. This is one of his most famous poetry:

Lie on a plane Two rectangles and many line segments.

Ah, gentle rectangles! All your sides parallel to X-axis or Y-axis. And one of you strictly encircles the other one Without any touch! The best place in the world The area between you two is.

Stupid line segments! Why you run across my darling rectangles? I will try all I can to clear you off the best place.

Darwin expressed his hatred towards line segments because they run into the area between the two rectangle (blue area in the above picture). He wanted to clear segments in that area. Given the rectangles and all the segments on the plane, please calculate the total length of segments Darwin needs to clear.

Note that segments are independent of each other, that is to say, Darwin has to clear the segments one by one even they may cover the same place. Segments coinciding with the boundaries of rectangles don't count into result.

Input

There are multiple test cases. The first line of the input will be an integer $T$ ($T \leq 20$) indicating the number of test cases.

For each case, the first line contains eight integers: $P_x$, $P_y$, $L_1$, $W_1$, $Q_x$, $Q_y$, $L_2$, $W_2$. The lower left corner of the rectangle is at point $(P_x, P_y)$, its length on the $x$-axis is $L_1$ and on the $y$-axis is $W_1$. The lower left corner of the hole is at point $(Q_x, Q_y)$, with size of $L_2 \times W_2$.

An integer $N$ comes in the next line, which is the number of line segments. The following $N$ lines each with four integers give the line segments in this format: $S_x$ $S_y$ $T_x$ $T_y$, representing the two ends, $(S_x,S_y)$ and $(T_x,T_y)$, of each segments.

$1 \leq N \leq 10000$, $1 \leq L_2 < L_1 \leq 20000$, $1 \leq W_2 < W_1 \leq 20000$. All other numbers in the input would have absolute values no more than $10000$. For each segment, the two ends do not coincident.

Output

For each task, print Case #t: L in a single line, in which $t$ is the number of this case starting from $1$, and $L$ is the length Darwin needs to clear (rounded to two decimal place).

Samples

1
0 0 4 3 1 1 2 1
7
-1 0 1 0
0 1 2 3
1 3 1 -1
-1 4 1 4
2 0 4 3
2 1 4 1
4 0 2 2

Case #1: 10.25

Resources

10th UESTC Programming Contest Preliminary