Pentagon

You are given a pentagon. Find the number of its triangulations.

A triangulation of polygon $P$ is a collection of triangles such that the internal areas of these triangles have no common points, and their union is equal to $P$. Each vertex of each triangle must coincide with some vertex of the polygon. Each side of each triangle must either fully coincide with some side of the polygon or have exactly two common points (endpoints) with the border of the polygon.

The first line contains one integer $n$, the number of test cases ($1 \le n \le 10\,000$). Each test case is preceded by a single empty line.

Each test case describes one pentagon and consists of five lines. Each line contains two integers $x$ and $y$ separated by a single space: the coordinates of the next vertex of the pentagon, listed in clockwise or counter-clockwise order ($-100 \le x, y \le 100$). Every pentagon has no self-intersections and no self-touchings. No two adjacent sides of the polygon lie on the same line.

Print $n$ lines, one for each test case. Each line contains one integer: the number of different triangulations of the corresponding pentagon.

The figure below shows all possible triangulations of the first pentagon in the example.