전방향 일주 (큰 입력)

세계 곳곳을 자주 다니는 K는 최근 여행에서 샌프란시스코를 떠나 프랑크푸르트, 요하네스버그, 아부다비, 싱가포르, 도쿄를 거쳐 다시 샌프란시스코로 돌아왔다. 이 여행에서 K는 모든 경선과 만나는 닫힌 경로를 따라 지구를 한 바퀴 돌았다. 즉 어떤 경도를 잡아도 그 경도에 놓인 점이 경로 위에 적어도 하나 있다.

K는 이 여행이 그렇게 대단한 일주인지 확신하지 못한다. 북극으로 날아가 극 주위를 걸어서 한 바퀴 도는 것만으로도 같은 조건을 만족하기 때문이다. 그래서 K는 더 일반적인 개념을 정의했다. 전방향 일주는 극을 어디에 두어도 일주가 되는 닫힌 경로다. 지구를 구라고 할 때, 전방향 일주는 가능한 모든 반구와 만나는 구면 위의 닫힌 경로다. 반구의 경계에 닿기만 해도 만난 것으로 친다. 같은 조건을 다르게 쓰면, 전방향 일주는 가능한 모든 대원과 만난다. 대원은 구면 위에 그릴 수 있는 지름이 가장 큰 원이다.

반지름이 1인 구 위의 점 $N$개가 순서대로 주어진다. 이 점들을 순서대로 이은 경로가 전방향 일주인지 판정하라. 경로는 이웃한 두 점을 구면 위 최단 경로로 잇고, 마지막 점과 첫 점도 같은 방식으로 잇는다. 마지막 점과 첫 점을 포함해 이웃한 두 점은 원점과 한 직선 위에 있지 않다. 즉 서로 대척점이 아니고, 구면 위에서 같은 점을 가리키지도 않는다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 K가 들른 지점의 수 $N$이 주어지고, 이어지는 $N$개 줄에 정수 $X_i$, $Y_i$, $Z_i$가 한 줄에 세 개씩 주어진다. 목록의 $i$번째 점은 구면 위의 좌표 $\left(\dfrac{X_i}{\sqrt{X_i^2 + Y_i^2 + Z_i^2}}, \dfrac{Y_i}{\sqrt{X_i^2 + Y_i^2 + Z_i^2}}, \dfrac{Z_i}{\sqrt{X_i^2 + Y_i^2 + Z_i^2}}\right)$이다.

제한

• $1 \le T \le 200$
• $3 \le N \le 5000$
• 모든 $i$에 대해 $-10^6 \le X_i \le 10^6$
• 모든 $i$에 대해 $-10^6 \le Y_i \le 10^6$
• 모든 $i$에 대해 $-10^6 \le Z_i \le 10^6$
• 모든 $i$에 대해 $X_i$, $Y_i$, $Z_i$ 중 적어도 하나는 0이 아니다.
• 경로에서 이웃한 두 점은 어느 쪽도 다른 쪽의 상수배가 아니다. 마지막 점과 첫 점도 이웃한 두 점으로 본다. 즉 이웃한 두 점은 서로 대척점이 아니고 구면 위에서 같은 점도 아니다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 테스트 케이스 번호이고, $y$는 경로가 전방향 일주이면 YES, 아니면 NO이다.

예제 입력의 첫 번째 테스트 케이스에서 세 점은 구를 여덟 조각으로 나눈 한 조각의 꼭짓점이고, 경로는 그 조각의 테두리를 따라간다. 이 경로와 전혀 만나지 않는 반구가 많다.

두 번째 테스트 케이스의 여덟 점은 구에 내접하는 정육면체의 꼭짓점이다. 어떤 반구를 잡아도 경로의 일부를 품는다. 모든 값을 5로 나누어도 같은 점 집합이 되므로 답은 그대로다.

세 번째 테스트 케이스의 경로는 그 자체가 대원이므로 다른 모든 대원과 어딘가에서 만난다.

네 번째 테스트 케이스는 세 번째와 같은 세 점을 쓰되 앞의 두 점을 각각 두 번씩 지난다. 한 테스트 케이스에 같은 점을 여러 번 적어도 되고, 경로가 같은 점이나 같은 구간을 여러 번 지나가도 된다.