#1164 지뢰제거

17  1 s   128 MB  

Description

지뢰제거를 위해서 새로운 장비가 투입되었다. 이 장비를 이용하면 10 m × 10 m 정사각형 범위 안(경계 포함)에 있는 지뢰를 한꺼번에 제거할 수 있다. 1,000 m × 1,000 m 의 작업장에 묻힌 지뢰의 위치를 모두 알고 있다고 할 때 이 장치를 효과적으로 사용하기 위해서 한 번 사용하여 제거할 수 있는 최대 지뢰 개수를 계산하는 프로그램을 작성하시오. 위의 그림은 아래 ‘Sample Input’의 세 번째 경우를 나타낸 것이다. 그림에서 보이는 정사각형 영역에 이 장비를 사용하면 다섯 개의 지뢰를 한꺼번에 제거할 수 있으며, 이 수가 한 번 사용하여 제거할 수 있는 최대 지뢰 개수이다.

Input

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 한 줄에 지뢰의 개수를 뜻하는 하나의 정수 N (10 ≤ N ≤ 10,000)이 주어진 다음, N개의 좌표가 한 줄에 하나씩 주어진다. 각 좌표는 0이상 1,000이하의 두 정수로 주어지는데, 첫 번째 정수는 x-좌표를, 두 번째 정수는 y-좌표를 나타낸다. 모든 정수 사이에는 한 칸의 공백이 존재한다. 같은 좌표에 두 개 이상의 지뢰는 존재하지 않으며, 지뢰의 크기는 무시할 정도로 작다고 가정한다.

Output

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해서 한 번에 가장 많이 제거할 수 있는 지뢰의 수를 출력하시오.

Sample Input

Sample Output

3
4
10 10
20 20
30 30
40 40
15
36 33
15 27
35 43
42 36
21 49
27 12
9 40
26 13
26 40
36 22
18 11
29 17
30 32
23 12
35 17
27
40 10
26 11
6 13
53 15
18 16
23 18
33 16
42 20
10 21
3 27
6 43
13 37
16 27
15 46
23 26
23 49
30 23
30 37
33 47
37 23
40 40
46 48
40 29
43 28
49 25
46 30
44 33
2
5
5