한 번에 웜홀

당신은 은하 간 초공간 골프 대회에 참가하고 있으며, 결승 라운드에 진출했다! 당신은 반드시 우승하겠다고 굳게 결심했으므로, 승리 전략을 준비하고자 한다.

초공간 골프에서는 일반 골프와 마찬가지로 클럽으로 공을 쳐서 자신이 선택한 방향으로 보낸다. 초공간 골프의 경기장은 서로 다른 홀을 나타내는 점들이 있는 2-차원 평면이다. 공 역시 하나의 점으로 나타내며, 홀과 같은 위치가 아닌 한 공의 시작 위치를 선택할 수 있다.

초공간 골프이므로, 선수들은 몇몇 홀 쌍을 서로 연결해 웜홀로 만들 수 있다. 각 홀은 일반 홀로 남겨 두거나, 최대 하나의 다른 홀과 연결할 수 있다(자기 자신과는 절대 연결할 수 없다). 웜홀은 무방향 연결이며, 어느 방향으로든 통과할 수 있다.

환경에 마찰이 없으므로 공을 치면 공은 직선 방향으로 움직이며, 홀에 도달하지 않는 한 그 방향을 영원히 유지한다. 공이 도달한 홀을 h라고 하자. 홀 h에 닿았을 때, h가 다른 홀과 연결되어 있지 않으면 공은 멈춘다. h가 다른 홀 h'과 연결되어 있으면 공은 즉시 h'에서 나오며 이전과 같은 방향으로 계속 움직인다.

각 홀의 위치는 알고 있다. 한 번 공을 쳐서 닿을 수 있는 서로 다른 홀의 수를 최대화하고자 한다. 이를 위해 공의 시작 위치와 공을 보낼 방향, 그리고 웜홀로 연결할 홀 쌍이 있다면 그 쌍들을 선택하고자 한다. 공은 웜홀과 같은 위치에서 출발할 수 없다. 공이 웜홀을 통과하면, 공이 들어간 홀과 나온 홀을 모두 총합에 포함한다. 공이 어떤 홀에 여러 번 들어가거나 그 홀에서 여러 번 나오거나 둘 다 하더라도, 각 홀은 한 번만 센다. 공이 어떤 홀에서 멈추면 그 홀도 총합에 포함한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. -$10^{9}$ ≤ $X_{i}$ ≤ $10^{9}$, 모든 i에 대해. -$10^{9}$ ≤ $Y_{i}$ ≤ $10^{9}$, 모든 i에 대해. ($X_{i}$, $Y_{i}$) ≠ ($X_{j}$, $Y_{j}$), 모든 i ≠ j에 대해. (어떤 두 홀도 같은 좌표에 있지 않다.)

테스트 세트 1 (Visible Verdict)

1 ≤ N ≤ 7.

테스트 세트 2 (Hidden Verdict)

1 ≤ N ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 홀의 총개수를 나타내는 단일 정수 N이 있는 한 줄로 시작한다. 이어지는 N개의 줄에는 각각 두 정수 $X_{i}$와 $Y_{i}$가 주어지며, 이들은 각각 i번째 홀의 X좌표와 Y좌표를 나타낸다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 위에서 설명한 대로 최적의 결정을 내렸을 때 닿을 수 있는 서로 다른 홀의 최대 개수이다.

예제 케이스 #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에서는 홀이 하나뿐이며, 웜홀을 전혀 고려할 필요 없이 그 홀로 공을 칠 수 있다. (참고로 홀 좌표에 허용되는 범위 밖이라도 원하는 어떤 시작 위치든 선택할 수 있다.)