众所周知，山脉是有限区域内高出周围地表的巨大地形。如果我们作为游客拍摄了一张远山的照片并将其打印出来，纸面上的图像将呈现为一个特定的多边形。

从数学角度来看，我们可以将照片中山脉的范围描述为一系列不同的点，记为 $(x_1, y_1)$ 到 $(x_n, y_n)$。第一个点位于坐标系原点，最后一个点位于 $x$ 轴上。其余所有点的 $y$ 坐标均为正数，且 $x$ 坐标递增。具体而言，所有 $x$ 坐标满足 $0 = x_1 < x_2 < x_3 < \dots < x_n$。除第一个点和最后一个点的 $y$ 坐标为零外，其余所有点的 $y$ 坐标均为正数。

山脉的范围是一个多边形，其边界依次经过点 $(x_1, y_1)$ 到 $(x_n, y_n)$，并回到第一个点。在本题中，你的任务是计算照片中山脉范围的面积。

输入格式

输入包含多组测试数据，第一行描述一个整数 $t$ ($1 \le t \le 20$)，表示测试数据的总数。

对于每组测试数据，第一行提供一个整数 $n$ ($1 \le n \le 100$)，表示用于描述山脉范围的点数。接下来的 $n$ 行描述所有点，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($0 \le x_i, y_i \le 1000$)，表示第 $i$ 个点的坐标。

输出格式

对于每组测试数据，输出一行面积，保留 6 位小数。

样例

输入 1

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

1.000000
125.000000
60.500000