Distinct Distances

You are setting up a scavenger hunt in the two-dimensional plane.

You have already chosen $n$ distinct points of interest, labeled $p_1, p_2, \dots, p_n$. Point $p_i$ sits at the integer coordinates $(x_i, y_i)$.

Now you want to choose one more point $q$ for the final location. The coordinates of $q$ must be finite, but they do not have to be integers. Point $q$ may coincide with one of the points $p_i$.

To make the final location interesting, you want to minimize how many distinct distances there are from $q$ to the chosen points. Formally, choose $q$ that minimizes $|S(q)|$, where

$S(q) = \{\,|q - p_1|,\ |q - p_2|,\ \dots,\ |q - p_n|\,\}.$

Here $|S(q)|$ is the number of elements of $S(q)$, and $|q - p_i|$ is the Euclidean distance between $q$ and $p_i$. $S(q)$ is a set, so if two or more of the distances $|q - p_i|$ are equal, they count as a single element.

Given the coordinates of the points, find the minimum value of $|S(q)|$.

Warning: inexact arithmetic may make it difficult to identify distances that are exactly equal.

The first line contains one integer $n$ ($1 \le n \le 40$).

Each of the next $n$ lines contains two space-separated integers $x_i$ and $y_i$ ($|x_i|, |y_i| \le 300$), the coordinates of $p_i$. The $n$ points are pairwise distinct.

Print on a single line the minimum number of distinct distances from $q$ to all of the points $p_i$.

In the first sample you can take $q = (0, 0)$, and every point is at distance 5. In the second sample you can take $q = (1.5, 1.5)$.