Description

Given a convex polygon with non-zero area, determine precisely its area. The coördinates of the polygon are integer.

Input

The first line of the input is a single integer (T) which specifies how many test cases (polygons) follow. T is between 1 and 1,000, inclusive. The following lines are the test cases, each representing a polygon. The first line of a test case is a single integer (n) which states how many vertices the polygon has. Then n lines follow, one for each vertex, each with two integers representing the x and the y coördinates of the vertex. The order the vertices are listed is important: between each pair of adjacent vertices, and between the first and the last, is an edge of the polygon.

Each coördinate integer is between 0 and 10,000, inclusive. Each polynomial has at most 50 vertices, and at least 3 vertices.

Output

For each test-case polygon from the input, output a line with a single float that represents the area of the polygon. Round the float to one digit right of the decimal point. No round-off error will be accepted. That is, your output must match precisely the judges' output exactly to be accepted.

Sample Input

4
3
1 2
1 1
2 1
3
12 7
0 0
9 5
3
4 183
342 101
419 7
5
100 97
0 0
258 11
291 23
293 64

Sample Output

0.5
1.5
12729.0
18319.5