Smoothed Gardens

Given a triangle and a rope loop longer than its perimeter, find the area traced by a stake held tight in the loop.

Medium5GeometryMathNo attempts yetTime limit2sMemory limit512 MB

Problem

The Flathead Fancy Landscaping Company's customers are too high-class to have gardens with straight edges, so Joe P. Flathead, the owner, has come up with a way to smooth out the contours. He puts a stake in each corner of a triangular plot and drops a loop of rope around the three stakes. Then, using a fourth stake in the loop, he pulls the rope tight to mark out a smoothed version of the triangle (see the figure below; the thinner lines are various positions of the rope). This process is similar to the method you learned in middle school to draw an ellipse using 2 push-pins, a piece of string, and a pencil, but J.P. Flathead uses three stakes (not two), a rope, and another stake instead of a pencil.

The longer the rope loop, the smoother the outline is (see the examples below):

To determine how much soil and how many plants the garden requires, Joe needs to find the area of the resulting smoothed outline.

Write a program that takes as input the coordinates of the corners of the triangle and the length of the rope loop, and outputs the area of the smoothed region. The coordinate system is chosen so that the first vertex is at the origin (A(0,0)A(0, 0)), the xx-axis runs along the line from the first vertex to the second vertex (B(Bx,0)B(B_x, 0)), and the final vertex is above the xx-axis (C(Cx,Cy)C(C_x, C_y)).

Input

The first line of input contains a single decimal integer PP (1P100001 \le P \le 10000), the number of data sets that follow.

Each data set is processed identically and independently. Each data set consists of a single line of input. It contains the data set number KK, followed by a single space, followed by 4 floating point values BxB_x, CxC_x, CyC_y (Bx>0B_x > 0, Cy>0C_y > 0), and the rope length LL, all measured in feet. The rope is longer than the perimeter of the triangle.

Output

For each data set there is one line of output. The line consists of the data set number KK, followed by a single space, followed by the area of the smoothed region in square feet, rounded to exactly 2 decimal places.