Metal

You are a metal artist making a piece of steelwork. You first mark $n$ points on a large steel board, then cut out from the board a polygon that connects those $n$ points. To perform the cut, you melt the board along the boundary of the polygon with two lasers that hang from a long horizontal bar suspended above the board, as shown in Figure 1. The bar is vertical, that is, parallel to the $y$-axis, and it moves continuously (never stopping) only in the positive $x$-direction, from the left side of the board toward the right side. Each laser can slide only along the bar, and the two lasers can never meet on the bar. Moreover, the bar advances monotonically from left to right and can never return to a position to the left of where it currently is.

These conditions imply that every polygon you can obtain is both simple and monotone. A polygon $P$ is simple if no two of its edges intersect, except that two adjacent edges meet only at their shared endpoint, and $P$ contains no holes. A polygon $P$ is monotone if its intersection with any vertical line is either empty, a single point, or a single line segment.

Figure 1. A cutting tool with two lasers hanging from a vertical bar.

To choose a good shape for your steelwork, you want to know how many different simple monotone polygons on the $n$ points exist. Your task is to compute that number. For example, Figure 2 shows an instance of seven points for which there are exactly four different simple monotone polygons.

Figure 2. Four different simple monotone polygons for a set of seven points.

The input is read from standard input. The first line contains the number of test cases $T$. Each test case starts with a line containing an integer $n$ ($3 \le n \le 50$), the number of points in $S = \{s_0, s_1, \ldots, s_{n-1}\}$. Each of the next $n$ lines contains two nonnegative integers $x_i$ and $y_i$ ($0 \le x_i, y_i \le 200000$), meaning that point $s_i$ has coordinates $(x_i, y_i)$. No two points of $S$ have the same $x$-coordinate.

For each test case, write to standard output a single line containing the number of different simple monotone polygons that connect the $n$ points of $S$.