Special Tetrahedron

Time Limit: 2000ms
Memory Limit: 65536KB
This problem will be judged on HDU. Original ID: 5839
64-bit integer IO format: %I64d      Java class name: Main

Description

Given $n$ points which are in three-dimensional space(without repetition).

Please find out how many distinct Special Tetrahedron among them. A tetrahedron is called Special Tetrahedron if it has two following characters.

1. At least four edges have the same length.

2. If it has exactly four edges of the same length, the other two edges are not adjacent.

Input

Intput contains multiple test cases.

The first line is an integer $T, 1 \leq T \leq 20$, the number of test cases.

Each case begins with an integer $n(n \leq 200)$, indicating the number of the points.

The next $n$ lines contains three integers $x_i,y_i,z_i$, $(-2000 \leq x_i,y_i,z_i \leq 2000)$, representing the coordinates of the ith point.

Output

For each test case,output a line which contains"Case #x: y",x represents the xth test(starting from one),y is the number of Special Tetrahedron.

Sample Input

2
4
0 0 0
0 1 1
1 0 1
1 1 0
9
0 0 0
0 0 2
1 1 1
-1 -1 1
1 -1 1
-1 1 1
1 1 0
1 0 1
0 1 1

Sample Output

Case #1: 1
Case #2: 6

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .