Cocircular Points

Time limit5sMemory limit128 MB

Summary

For each test case with up to 100 distinct points, find the largest subset that lies on one common circle and print its size.

Level: Medium7 of 10
Topics: Geometry, Hash map, Combinatorics, Brute force
Solved: No attempts yet

Problem

A set of collinear points is a set of points that all lie on a single straight line. Analogously, a set of cocircular points can be defined as a set of points that all lie on a single circle.

Given a set of points, write a program that finds the size of the largest subset of these points that is cocircular (that is, all points of the subset lie on one common circle).

Input

The input consists of several test cases.

The first line of each test case contains the number of points $N$ ( $1 \le N \le 100$ ). Each of the next $N$ lines contains the coordinates $X$ and $Y$ of a point ( $-10^4 \le X, Y \le 10^4$ ), separated by a space. No two points share the same coordinates.

The last line of the input contains a single $0$ , which marks the end of the input.

Output

For each test case, print on its own line the size of the largest subset of the given points that can lie on a single circle.

Examples1

Example 1

Input

7
-10 0
0 -10
10 0
0 10
-20 10
-10 20
-2 4
4
-10000 10000
10000 10000
10000 -10000
-10000 -9999
3
-1 0
0 0
1 0
0

Expected output

5
3
2