A prominent artist decided to create a series of original paintings, all of them with the shape of a convex polygon. His idea is to partition every polygon into triangles, by drawing a set of non-intersecting line segments (called diagonals) that connect two non-consecutive vertices of the polygon. Then, triangles will be coloured with oil paint, and diagonals will be coloured with 22-carat gold bands. But, as gold is expensive, he wants to know the minimum amount of gold band required by each polygon.

     

Given a polygon and one of its partitions into triangles, the amount of gold band required by the partition is the sum of the lengths of its diagonals. The minimum amount of gold band required by a polygon is the least amount of gold band required by any of its partitions.

Problem

Write a program that, given a sequence of convex polygons, computes the minimum amount of gold band required by each polygon.

Input

The first line contains an integer N (1 <= N <= 20), which is the length of the sequence of polygons. The following lines contain N polygon descriptions.

The first line of a polygon description contains an integer V (4 <= V <= 400), which is the number of vertices of the polygon.

The following V lines list the polygon vertices in a clockwise direction. Each line contains two integers, separated by a space, which are the x-coordinate and the y-coordinate of a polygon vertex (where -300000 <= x-coordinate <= 300000 and -300000 <= y-coordinate <= 300000).

Output

The output consists of N lines. The i^th line contains the minimum amount of gold band required by the i^th polygon, rounded to 2 decimal places.

Sample Input

2
5
0 0
0 100
40 150
100 100
100 0
4
100 903
120 740
80 600
-50 700

241.42
174.64