无畏的环球旅行者 K（她可能是本题的作者）最近一直在旅行。在最近的一次旅行中，她从旧金山出发，途经法兰克福、约翰内斯堡、阿布扎比、新加坡、东京，最后回到旧金山。在这次旅行中，她通过沿着一条经过每一条经线的闭合路径行进，完成了环球航行。换句话说，对于每一条可能的经线，这条路径上至少有一个点位于该经线上。

然而，K 不确定这次旅行是否称得上“超级棒”，因为通过飞往北极然后绕着它走一圈也可以环绕地球，这看起来并不特别困难（除了飞往北极的那部分）。因此，她决定提出一个更广义的环球航行定义。这个新概念被称为“全方位环球航行”（omnicircumnavigation）——即地球（我们假设其为球体）上的一条闭合路径，无论极点位于何处，它都是一次环球航行。换句话说，全方位环球航行是球面上的一条闭合路径，它触及了每一个可能的半球。（触及半球的边缘也算。）等价地，全方位环球航行与每一个可能的大圆（球面上直径最大的圆）相交。

给定球面上半径为 1 的 $N$ 个点。你需要检查按顺序连接这些点的路径是否为全方位环球航行。该路径由连接每一对相邻点（包括最后一个点和第一个点）的最短球面路径组成。任意两个相邻点（包括最后一个点和第一个点）不与原点共线。（也就是说，它们不是对跖点——即极点——且它们在球面上不代表同一个点。）

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$，表示 K 访问的城市数量。接下来的 $N$ 行每行包含三个整数 $X_i, Y_i, Z_i$。列表中的第 $i$ 个点由坐标 $(X_i / \sqrt{X_i^2 + Y_i^2 + Z_i^2}, Y_i / \sqrt{X_i^2 + Y_i^2 + Z_i^2}, Z_i / \sqrt{X_i^2 + Y_i^2 + Z_i^2})$ 给出。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是用例编号，$y$ 为 YES 或 NO，取决于该路径是否为全方位环球航行。

数据范围

$1 \le T \le 200$ $-10^6 \le X_i, Y_i, Z_i \le 10^6$，对于所有 $i$。 对于所有 $i$，$(X_i, Y_i, Z_i)$ 中至少有一个值不为 0。 对于所有满足 $(i + 1 = j)$ 或 $(i = N - 1 \text{ 且 } j = 0)$ 的 $i, j$，$(X_i, Y_i, Z_i)$ 和 $(X_j, Y_j, Z_j)$ 中没有一个是另一个的整数倍。（即任意两个相邻点，包括最后一个和第一个，不是对跖点，也不代表球面上同一个点。）

子任务 1 时间限制：20 秒 $3 \le N \le 50$

子任务 2 时间限制：100 秒 $3 \le N \le 5000$

样例

样例输入 1

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

样例输出 1

Case #1: NO
Case #2: YES
Case #3: YES
Case #4: YES

说明

在样例 1 中，这三个点是球面上一个卦限的表面点，路径勾勒出了该卦限。有许多半球与该路径完全不重叠。

在样例 2 中，这八个点是内接于球体的立方体的顶点；任何半球都将包含该路径的至少一部分。注意，将所有值除以 5 会产生一个等价的用例（具有相同的点集）。

在样例 3 中，路径本身就是一个大圆，因此其他每一个大圆都必须在某处与它相交。

样例 4 使用了与样例 3 相同的三个点，只是前两个点各被访问了两次。注意，一个用例可能包含同一个点的多个表示，并且路径可能多次包含相同的点或连接。