题目描述

Johnny 是一位非常年轻的数学家，但他此刻正在为他妹妹的数学作业烦恼。

这个周末，他的妹妹需要完成一项作业，计算各种几何图形的对称轴数量。因为 Johnny 这个周末想要去海边旅行，所以他希望他的妹妹能尽快完成这项作业。

于是他找到了擅长编程的你，你一定能帮助他完成这项任务的！

输入格式

输入包含多组数据。

第一行包含一个整数 $t$，代表数据的组数。

对于每组数据，第一行一个整数 $n$，代表多边形的顶点数。

接下来 $n$ 行，每行两个整数 $x_i,y_i$，代表每个顶点的坐标。

输入中的第 $i$ 个顶点会与第 $i+1$ 个顶点连一条边。特别地，输入中的第 $n$ 个顶点会与第一个顶点连一条边。

输入给出的多边形不保证是凸多边形，但是保证任意两条边只会在端点处相交，且任意两条相邻的边不共线。

输出格式

对于每组数据，输出一行一个整数，即多边形对称轴的数量。

样例

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

数据范围

$1 \leq t \leq 10$，$3 \leq n \leq 10^5$，$-10^8 \leq x_i,y_i \leq 10^8$。