International Programming ContestApril 19, 2003, Blagoevgrad, Bulgaria

Sponsored by  

Task G. Columns In The Room

Room is a square of side N (5ЈNЈ10000) and the corners of the room are presented with the points (0,0), (0,N), (N,0) and (N,N) in an orthogonal coordinate system. Let K columns with rectangular form and sides parallel to the coordinate axes are placed around the room (1ЈKЈ100). The columns could not overlap and touch them self but it is possible that a column touch a side of the room. Write a program G.EXE to find the shortest path from bottom left to the top right corner of the room. The path could touch the sides of the columns and the walls of the room but could not cross them.

Input

The input data will be in the standard input. In the first line the number T of the tests examples that the program has to solve will be given. In the first line of a test example the numbers N and K will be given separated by an interval. Each of the next K lines of the test contains the four integers X₁, Y₁, X₂, Y₂, separated each other by an interval, that describe the position of one column – (X₁,Y₁) are the coordinates of the bottom left and (X₂,Y₂) – the coordinates of the top right corner of the column, X₁< X₂, Y₁<Y₂.

Output

The length of the shortest path found by the program has to be printed on the standard output. Three digits after the decimal point will be considered.

Sample Input

2

20 3

4 0 9 6

16 4 19 20

6 7 15 14

20 3

16 6 20 10

8 0 10 10

0 12 14 16

Sample Output

38.522432

29.130804