该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile2651.zip](file://AdditionalFile2651.zip?type=additional_file)

#2651. 「POI2007 R1」对称轴 Axes of Symmetry

标签: 传统 | 时间限制: 3500 ms | 内存限制: 32 MiB |

题目描述

译自 POI 2007 Stage 1.「Osie symetrii」

给定一个多边形，不一定是凸多边形，但没有自交，即除了相邻的边在顶点上相交外没有两条边有公共点。

求多边形的对称轴个数。

输入格式

第一行一个整数 $t (1 \le t \le 10)$，表示测试点个数。

接下来有 $t$ 组数据，每组数据第一行有一个整数 $n (3 \le n \le 100\ 000)$，表示多边形的点数。

接下来 $n$ 行每行有两个整数 $x$ 和 $y$ （$-100\ 000\ 000 \le x \le 100\ 000\ 000$，$-100\ 000\ 000 \le y \le 100\ 000\ 000$），表示多边形的点。保证相邻边不共线。

输出格式

输出 $t$ 行，对每个多边形输出一个整数表示对称轴的个数。

样例

输入

2
12
1 -1
2 -1
2 1
1 1
1 2
-1 2
-1 1
-2 1
-2 -1
-1 -1
-1 -2
1 -2
6
-1 1
-2 0
-1 -1
1 -1
2 0
1 1

输出

4
2