Intrepid globetrotter K, who may or may not be the author of this problem, has been traveling a lot lately. On one of her recent trips, she traveled from San Francisco to Frankfurt to Johannesburg to Abu Dhabi to Singapore to Tokyo and back to San Francisco. On this trip, she circumnavigated the Earth by traveling along a closed path that touches every meridian. In other words, for every possible longitude, there is at least one point along this path at that longitude.

K is not sure that this trip qualifies as being *super awesome*, however,
since it would also be possible to circumnavigate the Earth by flying to the
North Pole and then walking around it, which does not seem to be particularly
difficult (other than the part about flying to the North Pole). So she has
decided to come up with a more generalized definition of circumnavigation.
The new concept is called *omnicircumnavigation* — a closed path
around the Earth (which we assume to be a sphere) that is a circumnavigation
regardless of where one places the poles. In other words, an
omnicircumnavigation is a closed path on the surface of a sphere that touches
every possible hemisphere. (Touching the edge of a hemisphere is sufficient.)
Equivalently, an omnicircumnavigation intersects every possible great circle
— a circle of greatest possible diameter on the surface of a sphere.

You are given a sequence of **N** points on a sphere of radius 1. You need
to check whether a path connecting those points in order is an
omnicircumnavigation. The path is formed by connecting each pair of
successive points along the shortest possible surface route, and connecting
the last point to the first one in the same way. No two successive points
(including the pair of the last point and the first point) are collinear with
the origin. (That is, they are not antipodes — polar opposites —
and they do not represent the same point on the surface of the sphere.)

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each begins with one line containing **N**,
the number of cities visited by K. The next **N** lines contain three
integers **X _{i}**,

For each test case, output one line containing `Case #x: y`

,
where `x`

is the case number and `y`

is either
`YES`

or `NO`

depending on whether the route is an
omnicircumnavigation or not.

1 ≤ **T** ≤ 200.

-10^{6} ≤ **X _{i}** ≤ 10

-10

-10

At least one of the values in (

3 ≤ **N** ≤ 50.

3 ≤ **N** ≤ 5000.

Input |
Output |

4 3 1 0 0 0 1 0 0 0 1 8 5 5 5 5 -5 5 -5 -5 5 -5 5 5 -5 5 -5 -5 -5 -5 5 -5 -5 5 5 -5 3 1 0 0 -1 1 0 -1 -1 0 5 1 0 0 -1 1 0 2 0 0 -2 2 0 -1 -1 0 |
Case #1: NO Case #2: YES Case #3: YES Case #4: YES |

In Sample Case #1, the three points are the surface points of one octant of the sphere, and the path traces out that octant. There are many hemispheres that do not overlap that path at all.

In Sample Case #2, the eight points are the corners of a cube inscribed in the sphere; any hemisphere will contain at least some parts of that path. Note that dividing all values by 5 would produce an equivalent case (with the same set of points).

In Sample Case #3, the path is itself a great circle, and so every other great circle must intersect it somewhere.

Sample Case #4 uses the same three points as in Sample Case #3, except that the first two points are visited twice each. Note that a case may include multiple representations of the same point, and that a path may include the same points or connections more than once.

Points | Correct | Attempted |
---|---|---|

15pt | 16 | 20 |

20pt | 6 | 12 |