Parallelogram Counting

Interview

Time limit1sMemory limit128 MB

Summary

Given n points, count how many 4-point subsets form a parallelogram by pairing points that share a midpoint.

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

Problem

You are given $n$ distinct points in the plane, each with integer coordinates. Count the number of parallelograms whose four vertices are all among these points.

Formally, count the $4$ -element subsets that can be labeled $\{A, B, C, D\}$ so that $AB \parallel CD$ and $BC \parallel AD$ . No four of the given points are collinear.

Input

The first line contains an integer $t$ ( $1 \le t \le 10$ ), the number of test cases. The test cases follow.

For each test case, the first line contains an integer $n$ ( $1 \le n \le 1000$ ). Each of the next $n$ lines contains two space-separated integers $x$ and $y$ ( $|x|, |y| \le 10^9$ ), the coordinates of one point.

Output

Print $t$ lines. The $i$ -th line contains the number of parallelograms for the $i$ -th test case.

Examples3

Example 1

Input

Expected output

5
6

Example 2
Input
```
1
4
0 0
1 0
1 1
0 1
```
Expected output
```
1
```

Example 3

Input

Expected output

1
1