SP175 POLY1 - Polygon

如果两个三角形的内部至少有一个公共点，我们便称这两个三角形相交。一个多边形是凸多边形，当且仅当任意两点之间的线段都完全在多边形内。如果一个三角形的顶点也是凸多边形的顶点，那么这个三角形就被称为该多边形的基本三角形。将一个凸多边形进行三角剖分，指的是将其划分为若干个基本三角形，并要求这些三角形互不相交，且它们的组合要完全覆盖整个多边形。现给定一个凸多边形及其三角剖分，请问该多边形的一个基本三角形最多可以与剖分中的多少个三角形相交。

第一行输入一个整数 $t$，表示测试用例的数量。接下来是 $t$ 个测试用例，每个测试用例之间用空行分隔。 每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 1000$），表示多边形的顶点数。顶点按顺时针方向编号为 $0$ 到 $n-1$。接下来的 $n-2$ 行描述了三角剖分中的每个三角形，每行有三个整数，表示第 $i$ 个三角形的顶点编号，这里 $1 \leq i \leq n-2$。

对于每个测试用例，输出一个整数，表示对于给定的三角剖分，该多边形的一个基本三角形能够相交的最大三角形数量。 **本翻译由 AI 自动生成**