题目描述

All as we know, a mountain is a large landform that stretches above the surrounding land in a limited area. If we as the tourists take a picture of a distant mountain and print it out, the image on the surface of paper will be in the shape of a particular polygon.

From mathematics angle we can describe the range of the mountain in the picture as a list of distinct points, denoted by $(x_1, y_1)$ to $(x_n, y_n)$. The first point is at the original point of the coordinate system and the last point is lying on the $x$-axis. All points else have positive $y$ coordinates and incremental $x$ coordinates. Specifically, all $x$ coordinates satisfy $0 = x_1 < x_2 < x_3 < ... < x_n$. All $y$ coordinates are positive except the first and the last points whose $y$ coordinates are zeroes.

The range of the mountain is the polygon whose boundary passes through points $(x_1, y_1)$ to $(x_n, y_n)$ in turn and goes back to the first point. In this problem, your task is to calculate the area of the range of a mountain in the picture.

输入格式

The input has several test cases and the first line describes an integer $t (1 \le t \le 20)$ which is the total number of cases.

In each case, the first line provides the integer $n (1 \le n \le 100)$ which is the number of points used to describe the range of a mountain. Following $n$ lines describe all points and the $i$-th line contains two integers $x_i$ and $y_i (0 \le x_i, y_i \le 1000)$ indicating the coordinate of the $i$-th point.

输出格式

For each test case, output the area in a line with the precision of $6$ digits.

3
3
0 0
1 1
2 0
4
0 0
5 10
10 15
15 0
5
0 0
3 7
7 2
9 10
13 0

1.000000
125.000000
60.500000