In a 2D plane N persons are standing and each of them has a gun in his hand. The plane is so big that the persons can be considered as points and their locations are given as Cartesian coordinates. Each of the N persons fire the gun in his hand exactly once and no two of them fire at the same or similar time (the sound of two gun shots are never heard at the same time by anyone so no sound is missed due to concurrency). The hearing ability of all these persons is exactly same. That means if one person can hear a sound at distance R₁, so can every other person and if one person cannot hear a sound at distance R₂ the other N-1 persons cannot hear a sound at distance R₂ as well.

The N persons are numbered from 1 to N. After all the guns are fired, all of them are asked how many gun shots they have heard (not including their own shot) and they give their verdict. It is not possible for you to determine whether their verdicts are true but it is possible for you to judge if their verdicts are consistent. For example, look at the figure above. There are five persons and their coordinates are (1, 2), (3, 1), (5, 1), (6, 3) and (1, 5) and they are numbered as 1, 2, 3, 4 and 5 respectively. After all five of them have shot their guns, you ask them how many shots each of them have heard. Now if there response is 1, 1, 1, 2 and 1 respectively then you can represent it as (1, 1, 1, 2, 1). But this is an inconsistent verdict because if person 4 hears 2 shots then he must have heard the shot fired by person 2, then obviously person 2 must have heard the shot fired by person 1, 3 and 4 (person 1 and 3 are nearer to person 2 than person 4). But their opinions show that Person 2 says that he has heard only 1 shot. On the other hand (1, 2, 2, 1, 0) is a consistent verdict for this scenario so is (2, 2, 2, 1, 1). In this scenario (5, 5, 5, 4, 4) is not a consistent verdict because a person can hear at most 4 shots.

Given the locations of N persons, your job is to find the total number of different consistent verdicts for that scenario. Two verdicts are different if opinion of at least one person is different.

Input

The first line of input will contain T (≤ 550) denoting the number of cases.

Each case starts with a line containing a positive integer N. Each of the next N lines contains two integers x_i y_i (0 ≤ x_i, y_i ≤ 30000) denoting a co-ordinate of a person. Assume that all the co-ordinates are distinct.

1)      For 10 cases, N = 1000.

2)      For 15 cases, 100 ≤ N < 1000.

3)      For others, N < 100.

Output

For each case, print the case number and the total number of different consistent verdicts for the given scenario.

2

3

1 1

2 2

4 4

2

1 1

5 5

Case 1: 4

Case 2: 2

Problem Setter: Shahriar Manzoor, Special Thanks: Jane Alam Jan

題目描述：

從每個點發出聲響，問最多有幾個不同的時間會讓感測器感測。

題目解法：

用 O(n^2) 把所有點距離算出來，並且去除重覆。
一開始使用 std::set 一直 TLE，還以自己錯了。
後來改用 sort 去計算，但仍然鄰近 TLE，雖然是 AC 了，最後使用基數排序。

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int S[1048576];
int T[1048576];
void RadixSort(int *A, int *B, int n) {
    int a, x, d, *T, C[256];
    for(x = 0; x < 4; x++) {
        d = x*8;
        for(a = 0; a < 256; a++)     C[a] = 0;
        for(a = 0; a < n; a++)      C[(A[a]>>d)&255]++;
        for(a = 1; a < 256; a++)    C[a] += C[a-1];
        for(a = n-1; a >= 0; a--)   B[--C[(A[a]>>d)&255]] = A[a];
        T = A, A = B, B = T;
    }
}
int main() {
    int testcase, cases = 0, n;
    int x[1005], y[1005];
    int pow2[30005];
    int i, j;
    for(i = 0; i < 30005; i++)
        pow2[i] = i*i;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            scanf("%d %d", &x[i], &y[i]);
        int m = 0, ret = 1;
        int *px, *py, *qx, *qy;
        px = x, py = y;
        for(i = 0; i < n; i++) {
            qx = x+i+1, qy = y+i+1;
            for(j = i+1; j < n; j++) {
                S[m++] = pow2[abs((*px)-(*qx))] + pow2[abs((*py)-(*qy))];
                qx++, qy++;
            }
            px++, py++;
        }
        RadixSort(S, T, m);
        px = S, qx = S+1;
        for(i = 1; i < m; i++, px++, qx++)
            if((*px) != (*qx))
                ret++;
        ret++;
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}