완전 일주 (Small)

여행이 잦은 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$
• 모든 $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$이 아니다
• 번호는 $0$부터 $N - 1$까지 붙인다. $i + 1 = j$이거나 $i = N - 1$이고 $j = 0$인 모든 $i$, $j$에 대해 $(X_i, Y_i, Z_i)$와 $(X_j, Y_j, Z_j)$는 어느 쪽도 다른 쪽의 상수배가 아니다
• $3 \le N \le 50$

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

첫 번째 예제의 1번 케이스에서 세 점은 구를 여덟 등분한 팔분면의 꼭짓점이고, 경로는 그 팔분면의 테두리를 그린다. 이 경로와 전혀 만나지 않는 반구가 많다.

2번 케이스에서 여덟 점은 구에 내접하는 정육면체의 꼭짓점이고, 어떤 반구를 잡아도 경로의 일부를 품는다. 모든 값을 $5$로 나눠도 같은 점 집합이 나오므로 답도 같다.

3번 케이스에서는 경로 자체가 대원이므로 다른 모든 대원이 이 경로와 어딘가에서 만난다.

4번 케이스는 3번 케이스의 세 점을 그대로 쓰되 앞의 두 점을 각각 두 번씩 들른다. 한 테스트 케이스에 같은 점을 여러 방식으로 적은 입력이 들어올 수 있고, 경로가 같은 점이나 같은 구간을 여러 번 지날 수 있다.