웜홀 홀인원

당신은 은하 간 초공간 골프 대회에 출전해 결승 라운드까지 올라갔습니다. 반드시 우승하고 싶어서 이길 전략을 미리 준비하려고 합니다.

초공간 골프에서도 일반 골프처럼 클럽으로 공을 치고, 공이 나아갈 방향은 직접 고릅니다. 경기장은 구멍을 나타내는 점들이 놓인 2차원 평면입니다. 공도 점으로 표시되며, 시작 위치는 구멍과 같은 자리만 아니면 자유롭게 고를 수 있습니다.

선수는 구멍 몇 쌍을 서로 연결해 웜홀로 만들 수 있습니다. 각 구멍은 일반 구멍으로 남겨 두거나, 다른 구멍 하나에만 연결할 수 있습니다(자기 자신과는 연결할 수 없습니다). 웜홀은 방향이 없어서 공이 어느 쪽으로든 통과할 수 있습니다.

환경에는 마찰이 없습니다. 공을 치면 직선으로 움직이며, 구멍 h에 닿기 전까지 그 방향을 계속 유지합니다. 공이 h에 닿았을 때 h가 다른 구멍과 연결되어 있지 않으면 공은 멈춥니다. h가 다른 구멍 h'와 연결되어 있으면 공은 곧바로 h'에서 나와 처음과 같은 방향으로 계속 움직입니다.

각 구멍의 위치는 알고 있습니다. 한 번 쳐서 닿을 수 있는 서로 다른 구멍의 수를 최대로 만들고 싶습니다. 이를 위해 공의 시작 위치, 공을 보낼 방향, 그리고 웜홀로 연결할 구멍 쌍(없을 수도 있음)을 고릅니다. 공은 웜홀과 같은 자리에서 시작할 수 없습니다. 공이 웜홀을 통과하면 들어간 구멍과 나온 구멍 모두 총합에 포함됩니다. 공이 같은 구멍에 여러 번 드나들어도 각 구멍은 한 번만 셉니다. 공이 어떤 구멍에서 멈추면 그 구멍도 포함됩니다.

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어집니다. 이어서 T개의 테스트 케이스가 나옵니다. 각 케이스는 구멍의 총 개수 N을 나타내는 정수 한 개로 시작합니다. 그다음 N줄에는 i번째 구멍의 X 좌표와 Y 좌표를 나타내는 정수 두 개 Xi, Yi가 각각 주어집니다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력합니다. x는 테스트 케이스 번호(1부터 시작)이고, y는 위에서 설명한 대로 최적으로 결정했을 때 닿을 수 있는 서로 다른 구멍의 최대 개수입니다.

1 <= T <= 100

모든 i에 대해 $-10^9 \le X_i \le 10^9$

모든 i에 대해 $-10^9 \le Y_i \le 10^9$

모든 $i \ne j$에 대해 $(X_i, Y_i) \ne (X_j, Y_j)$ (같은 좌표에 놓인 구멍은 없습니다)

예제 케이스 #1에서는 두 구멍을 웜홀로 연결하면 공을 둘 중 어느 구멍으로 보내도 두 구멍 모두에 닿을 수 있습니다. 웜홀이 없으면 공은 처음 닿은 구멍에서 멈추므로 두 개 이상에 닿을 수 없습니다.

예제 케이스 #2에서는 (0, 0) 구멍과 (5, 5) 구멍을 연결합니다. (4.9, 5)에서 수평 양의 방향으로 공을 치면 먼저 (5, 5) 구멍에 닿고, 그 구멍으로 들어가 (0, 0) 구멍에서 같은 수평 방향을 유지한 채 나옵니다. 마지막으로 (5, 0) 구멍에 닿고 멈춥니다. 이 구멍에는 연결된 웜홀이 없기 때문입니다.

예제 케이스 #3에서는 (0, 0)과 (5, 0) 구멍을 연결하고, (3, 2)와 (5, 5) 구멍도 연결합니다. (4, -1)에서 (5, 0) 구멍을 향해 공을 치면 (5, 0), (0, 0), (5, 5), (3, 2) 구멍에 이 순서대로 닿습니다.

예제 케이스 #4에서는 (0, 0)과 (1, 1), (2, 1)과 (11, 2), (8, 2)와 (14, 2) 구멍 쌍을 연결합니다. (-1, 0)에서 (0, 0) 구멍을 향해 공을 치면 (0, 0), (1, 1), (2, 1), (11, 2), (14, 2), (8, 2), (11, 2), (2, 1), (3, 1) 구멍에 이 순서대로 닿습니다. (11, 2)와 (2, 1) 구멍은 두 번씩 닿지만, 문제는 서로 다른 구멍의 수를 묻고 있으므로 각각 한 번만 셉니다.

예제 케이스 #5에서는 구멍이 하나뿐입니다. 웜홀을 고려할 필요 없이 그 구멍으로 공을 칠 수 있습니다. 시작 위치는 구멍 좌표의 범위 밖이라도 원하는 곳을 고를 수 있습니다.