给你一个五边形。你的任务是求出它的三角剖分数量。

多边形 $P$ 的三角剖分是指一组三角形的集合，满足这些三角形的内部区域没有公共点，且它们的并集等于 $P$。每个三角形的每个顶点必须与多边形的某个顶点重合。此外，每个三角形的每条边必须要么与多边形的某条边完全重合，要么与多边形的边界恰好有两个公共点（即端点）。

输入格式

输入的第一行包含一个整数 $n$，表示测试用例的数量（$1 \le n \le 10\,000$）。接下来是各个测试用例。在每个测试用例之前都有一个空行。

每个测试用例描述一个五边形，由五行组成。其中的每一行包含两个由单个空格分隔的整数 $x$ 和 $y$：按顺时针或逆时针方向给出的五边形下一个顶点的坐标（$-100 \le x, y \le 100$）。保证每个五边形都没有自交和自接触。此外，多边形的任意两条相邻边都不在同一条直线上。

输出格式

输出 $n$ 行，每个测试用例输出一行。每行必须包含一个整数：对应五边形的不同三角剖分数量。

样例

输入样例 1

2

-5 0
0 3
5 0
2 -2
-2 -2

-5 -5
-5 5
5 5
5 -5
0 0

输出样例 1

5
1

说明

该图展示了样例中第一个五边形的所有可能三角剖分。