Construction of highways

Time Limit: 3000 ms Memory Limit: 65536 KiB

Problem Description

China Qingdao International Horticultural Exposition 2014 (referred to as "Qingdao International Horticultural Expo") will "make life into a natural" as the theme park site is located in Forest Park, Qingdao Baiguoshan Lee Chang-eastern region.
In addition to the main venue - the Forest Park Baiguoshan, there are five sub-venues. In order to facilitate the general public as well as Qingdao visitors to travel around the world, the Qingdao Municipal Government decided to construct several highways to the venue in Qingdao five connected with the main venue. 
The main venue of the World Park and all sub-venues are convex polygons, and they are in a different position (no intersection), the city government hopes to save as much as possible funding to construct highways, so you need to design a program that all venues will be able to connect to each other through one or more highways and the distance of the highways is minimum.
 

Input

The input consists of multiple test cases. The first line contains an integer T means the number of test cases. For each case, first, a line with a number n, represents the main venue is the n-polygon, then input n lines, each containing vertex coordinates xi, yi; followed five groups of the same input, which means that the coordinates of the sub-venues. (n<=10000, -10000<=xi,yi<=10000)

Output

For each test case, output one line represents the minimum distance, the result correct to two decimal places.

Sample Input

1
4
0 3
-1 3
0 4
-1 4
4
3 3
4 3
3 4
4 4
4
7 3
8 3
7 4
8 4
4
0 0
0 -1
-1 0
-1 -1
4
3 0
4 0
3 -1
4 -1
4
7 0
8 0
7 -1
8 -1

Sample Output

15.00

Hint

 

Source

SDUST