Polygon Symmetry Axes

Little Johnny is trying to help his little sister Justina with her homework. She has been given various exercises asking to determine the number of axes of symmetry for given polygons. Your task is to write a program that reads the description of a polygon and determines the number of its symmetry axes.

More formally, you are given a polygon by its vertices listed in order (either clockwise or counter‐clockwise). You have to compute the number of lines (axes) such that when the polygon is reflected about any of these lines, it remains identical.

Note: If the polygon is symmetric, then the reflection of every vertex with respect to the axis must match the corresponding vertex of the polygon (within a small tolerance due to floating point precision).

The reflection of a point \(P=(x,y)\) about a line passing through points \(A=(x_a,y_a)\) and \(B=(x_b,y_b)\) is computed as follows:

[ \begin{aligned} d &= (x_b-x_a)^2+(y_b-y_a)^2,\ t &= \frac{(x-x_a)(x_b-x_a)+(y-y_a)(y_b-y_a)}{d},\ \text{Projection} &= \left(x_a+t(x_b-x_a),; y_a+t(y_b-y_a)\right),\ P' &= \left(2(x_a+t(x_b-x_a))-x, ; 2(y_a+t(y_b-y_a))-y\right). \end{aligned} ]

Your program should consider both types of potential symmetry axes:

• For even \(n\):
• An axis that goes through a pair of opposite vertices.
• An axis that goes through the midpoints of a pair of opposite edges.
• For odd \(n\):
  • An axis that goes through a vertex and the midpoint of the opposite edge.

If a candidate axis satisfies that for all pertinent indices \(k\) the reflection of vertex \(v_{i-k}\) is equal (within an epsilon tolerance \(\varepsilon = 10^{-6}\)) to vertex \(v_{i+k}\) (indices modulo \(n\)), then the axis is valid.

inputFormat

The input starts with an integer \(T\) (number of test cases). Each test case begins with an integer \(n\) (\(n \ge 3\)), which denotes the number of vertices of the polygon. Then follow \(n\) lines, each with two floating-point numbers representing the coordinates (\(x, y\)) of a vertex. The vertices are given in order (either clockwise or counter-clockwise).

outputFormat

For each test case, print a single line containing one integer: the number of axes of symmetry of the given polygon.

sample

3
4
0 0
0 1
1 1
1 0
3
0 0
1 0
0.5 0.8660254
5
0 0
2 0
3 1
1.5 2
0 1

4
3
0