2018 WUSTACM 新生交流群:829055498

Problem 2246. -- Match the Point

2246: Match the Point

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 9  Accepted: 1
[Submit][Status][Web Board]

Description

        Grven N integral points on plane, you are going to find a maximum matching which consists of edges with at most two kinds of lengths.

Input

        There are multiple test cases. The first integer T is the number of cases.
        In each case, the first line contains one positive integer(1 ≤ N ≤ 50), the number of points. N parirs of integers follows, indicating the coordinates of the points.

Output

        The output should contain T lines. Each line contains the size of maximum matching.

Sample Input

1
14
0 2 0 5 0 6 1 3 2 0 2 4 2 6 3 0 3 2 4 0 4 4 5 1 6 5 6 6

Sample Output

7

HINT

this is one of the solutions of sample data.


[Submit][Status][Web Board]