Continuous Drawing#1709

Continuous Drawing

1 second

64 megabytes

Very hard

A simple task! You are given the end points of some line segments. Just draw them. Too easy, right?

You decide to challenge yourself and therefore add some constraints.

Start from the end point of any line segment.
Do not lift your pen off the paper.
You can go over a line more than once.
Do not draw any line other than the given ones.
You can only change direction at integer values of $x$ and $y$ .
Use the minimum amount of ink needed.

You need $1$ unit of ink to draw one unit of line. The distance between neighboring points is $1$ unit.

So the distance (from $A 1$ to $B 1$ ) = $1$ unit, and the distance (from $A 1$ to $A 2$ ) = $1$ unit.

Input

The first line contains an integer $T$ ( $T < 20$ T < 20) indicating the number of test cases. Each test case starts with a line containing the number of segments $N$ ( $N < 10$ N < 10). The next $N$ lines describe the segments. Each segment is given by two points: $Y 1 X 1$ and $Y 2 X 2$ . $Y 1$ and $Y 2$ are in the range $[A, E]$ . $X 1$ and $X 2$ are in the range $[1, 5]$ . The first test case corresponds to the figure above. Pay attention to the input format.

Output

For each test case, print on a separate line the minimum amount of ink required to draw, rounded to two decimal places. If it is impossible to complete the drawing without lifting the pen, print x( (see output sample).

Examples

Example 1

Loading

T < 20

N < 10