I. Two Squared Equals Four
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yes, this problem is related to squares.

You are given a set $$$S$$$ of $$$n$$$ distinct points on the $$$xy$$$-plane, each with integer coordinates. A set of points $$$T$$$ is squarish if it contains exactly four points, and they can form the four vertices of a square.

Now, you have to remove exactly one point from $$$S$$$. Find the maximum number of squarish subsets of $$$S$$$ if you remove the point optimally.

In case you are not aware, three squared equals nine.

Input

Each test contains multiple test cases. The first line of each test contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$5 \le n \le 5000$$$) — the number of points in $$$S$$$.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i,y_i \le 10^9$$$) — the coordinates of the $$$i$$$-th point. It is guaranteed that the $$$n$$$ points are distinct.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, output the maximum number of squarish subsets of $$$S$$$ after removing exactly one point.

Example
Input
1
9
-1 1
-1 0
-1 -1
0 1
0 0
0 -1
1 1
1 0
1 -1
Output
4
Note

In the sample test case, one of the optimal solutions is to remove $$$(1,1)$$$. There will be $$$4$$$ squarish subsets in $$$S$$$, which are:

  • $$$\{(-1,1),(-1,0),(0,1),(0,0)\}$$$,
  • $$$\{(-1,-1),(-1,0),(0,-1),(0,0)\}$$$,
  • $$$\{(1,-1),(1,0),(0,-1),(0,0)\}$$$,
  • $$$\{(0,1),(-1,0),(0,-1),(1,0)\}$$$.