lykoo is a chinese girl pursuing the bachelor's degree in economics in Holland. Recently she found a part time job of sending newspapers to keep balance. It's really a hard job. Because lykoo needs to get up 4 o'clock every morning, first goes to the post office nearby to fetch newspapers, then delivers them to 8 bookstores. When she finished the work, it's usually about 6 o'clock and she will go back home to continue her sweet dream.
On QQ, wiltord usually heard her complaint about that job. As the best friend of lykoo, wiltord wants to help her choose the shortest round path, so that she has more time to sleep.


The first line of the input contains an integer T (T <= 1010) indicating the number of test cases. For each test case, ten pairs of integers will be given in a line; the first is the coordinate of lykoo's house, the second is the post office, the rests are eight bookstores. You may assume there is a straight road between each pair of them. Coordinate will be in the range of [0, 1000].


For each test case, print the minimum distance lykoo has to finish in a single line with precision of three decimal places.

Sample Input

0 0 1 0 2 0 3 0 4 0 4 1 3 1 2 1 1 1 0 1

Sample Output


Author: wiltord