The night sky can be modeled as an infinite 2D plane. There are N stars at distinct positions on this plane, the ith of which is at coordinates (Xi, Yi).
A boomerang constellation is a pair of distinct equal-length line segments which share a single endpoint, such that both endpoints of each segment coincide with a star's location.
Two boomerang constellations are distinct if they're not made up of the same unordered pair of line segments. How many distinct boomerang constellations can you spot?
Input
Input begins with an integer T, the number of nights on which you look out at the sky. For each night, there is first a line containing the integer N. Then, N lines follow, the ith of which contains the space-separated integers Xi and Yi.
Output
For the ith night, print a line containing "Case #i: " followed by the number of boomerang constellations in the night sky.
Constraints
1 ≤ T ≤ 50
1 ≤ N ≤ 2,000
-10,000 ≤ Xi, Yi ≤ 10,000
Explanation of Sample
On the first night, every pair of stars is a unique distance apart, so there are no boomerang constellations. On the second night, there are 4 boomerang constellations. One of them consists of the line segments (0,0)-(0,2) and (0,2)-(0,4).
Example input
Code: Select all
5
3
0 0
0 1
0 3
5
0 0
0 1
0 2
0 3
0 4
4
0 0
0 100
100 0
100 100
4
0 0
-3 4
0 5
-5 0
6
5 6
6 5
7 6
6 7
7 8
8 7Code: Select all
Case #1: 0
Case #2: 4
Case #3: 4
Case #4: 3
Case #5: 12