Isosceles Triangles

Time limit2sMemory limit128 MB

Summary

Given N integer points with no three collinear, count the triples that form an isosceles triangle.

Level: Medium6 of 10
Topics: Geometry, Hash map, Math, Brute force
Solved: No attempts yet

Problem

A triangle can be classified into three kinds by its side lengths. If all three sides have the same length it is equilateral; if all three sides have different lengths it is scalene; if two sides have the same length and the third side has a different length it is isosceles.

It is a known fact that points whose coordinates are all integers cannot be the vertices of an equilateral triangle.

You are given a set of distinct points with integer coordinates on the $XY$ plane, and no three points in the set lie on the same line. Among all ways of choosing three of the points, count how many choices form the vertices of an isosceles triangle.

Input

The input consists of several test cases. The first line of each test case contains an integer $N$ , the number of points in the set ( $3 \le N \le 1000$ ). Each of the next $N$ lines describes one point with two integers $X$ and $Y$ separated by a single space ( $1 \le X, Y \le 10^6$ ), the coordinates of the point. Within a single test case no two points share the same location and no three points are collinear.

The last test case is followed by a line containing a single $0$ , which marks the end of the input.

Output

For each test case, output on a single line one integer: the number of ways to choose three points that form the vertices of an isosceles triangle.

Examples1

Example 1

Input

5
1 2
2 1
2 2
1 1
1000 1000000
6
1000 1000
996 1003
996 997
1003 996
1003 1004
992 1000
0

Expected output

4
10