Omnicircumnavigation (Small)

K travels a lot. On a recent trip she flew from San Francisco to Frankfurt, then on to Johannesburg, Abu Dhabi, Singapore, Tokyo, and back to San Francisco. That trip circled the Earth along a closed path that touches every meridian. For every possible longitude, the path passes through at least one point at that longitude.

K is not satisfied with that definition. Flying to the North Pole and walking a small circle around it also touches every meridian, and the walking part is easy. So she uses a stronger condition. An omnicircumnavigation is a closed path that circles the Earth wherever the poles are placed. Treat the Earth as a sphere. In other words, an omnicircumnavigation is a closed path on the surface of a sphere that meets every possible hemisphere, and touching the edge of a hemisphere counts as meeting it. Put another way, an omnicircumnavigation crosses every possible great circle, a circle of the largest possible diameter on the surface of a sphere.

You are given $N$ points on a sphere of radius $1$, in order. Decide whether the path that visits them in that order is an omnicircumnavigation. The path joins each pair of successive points along the shortest route on the surface, and joins the last point back to the first one the same way. No two successive points lie on one line through the origin, including the pair made of the last point and the first point. They are never antipodal, and they are never the same point of the sphere.

The first line contains the number of test cases, $T$. Each test case begins with a line containing $N$, the number of cities K visited. Each of the next $N$ lines contains three integers $X_i$, $Y_i$ and $Z_i$. The $i$-th point of the list is the point with coordinates $\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)$.

Limits

• $1 \le T \le 200$
• $-10^6 \le X_i \le 10^6$, for all $i$
• $-10^6 \le Y_i \le 10^6$, for all $i$
• $-10^6 \le Z_i \le 10^6$, for all $i$
• At least one of $X_i$, $Y_i$, $Z_i$ is not $0$, for all $i$
• Indices run from $0$ to $N - 1$. For all $i$ and $j$ such that $i + 1 = j$, or such that $i = N - 1$ and $j = 0$, neither of $(X_i, Y_i, Z_i)$ and $(X_j, Y_j, Z_j)$ is a multiple of the other
• $3 \le N \le 50$

For each test case, print one line containing Case #x: y, where x is the test case number starting from $1$, and y is YES if the path is an omnicircumnavigation and NO if it is not.

In case 1 of the first example, the three points are the corners of one octant of the sphere and the path traces that octant. Many hemispheres miss the path completely.

In case 2, the eight points are the corners of a cube inscribed in the sphere, and every hemisphere holds some part of the path. Dividing all the values by $5$ gives the same set of points, so it gives the same answer.

In case 3, the path is itself a great circle, so every other great circle crosses it somewhere.

In case 4, the three points of case 3 are used again, with the first two of them visited twice. One test case can hold several representations of the same point, and a path can repeat points or connections.