Farmer John

Farmer John keeps many cows that graze in his fields. His cow Bessie is very lazy: to reach her food she always walks to the barn along the shortest possible route. To give Bessie more exercise, Farmer John puts up a few straight fences so that she can no longer take the direct route and has to walk around them.

You are given Bessie's starting position, the position of the barn that holds her food, and the positions of all the fences (each modelled as a straight line segment). Compute the minimum distance Bessie has to walk. She may not cross any fence, but she is allowed to touch a fence.

The first line contains a single integer: the number of test cases. Each test case has the following format.

• One line with four integers $B_x$, $B_y$, $F_x$, $F_y$ with $-10000 \le B_x, B_y, F_x, F_y \le 10000$: the location of Bessie and the location of the food.
• One line with one integer $N$ with $0 \le N \le 100$: the number of fences.
• $N$ lines, one per fence, each with four integers $x_1$, $y_1$, $x_2$, $y_2$ with $-10000 \le x_1, y_1, x_2, y_2 \le 10000$ and $x_1 \ne x_2$ or $y_1 \ne y_2$: the coordinates of the two endpoints of that fence.

Integers on the same line are separated by single spaces. Neither Bessie's location nor the food's location lies on a fence, and no two fences touch or overlap.

For each test case, output on its own line a single real number: the minimum walking distance, rounded to exactly six digits after the decimal point.