题目描述

多立方体（polycube）是通过将单位立方体（每条边长度为1）在一个或多个面粘合在一起形成的立体结构。左下角的图形不是多立方体，因为某些立方体沿边而非面连接。

在本题中，多立方体由三维整数格点 ((x, y, z)) 处的单位立方体构成。构建过程从中心在 ((0,0,0)) 的立方体开始，之后每一步添加的新立方体必须与已存在的某个立方体共享一个面，且不能与已存在的立方体重复。例如：

• 左上的1×1×5长方体可按顺序 ((0,0,0) \rightarrow (0,0,1) \rightarrow \dots \rightarrow (0,0,4)) 构建。
• 右上的2×2×2立方体按给定顺序逐步添加，每个新立方体均与已有立方体共面。

多立方体的表面积由单位正方形组成，面积为整数。编写程序，输入一系列三维格点，判断其是否构成合法多立方体。若是，计算表面积；否则，输出第一个不合法立方体的位置（从1开始计数）。

输入

第一行包含整数 (N)（(1 \leq N \leq 1000)），表示测试用例数。
每个测试用例格式如下：

1. 第一行包含整数 (P)（(1 \leq P \leq 100)），表示立方体数量。
2. 后续若干行，每行包含最多8个立方体中心坐标，格式为“(x,y,z)”，坐标间用空格分隔。

输出

对每个测试用例，输出一行：

• 若合法，输出“数据集编号 表面积”。
• 若不合法，输出“NO 第一个非法立方体的索引”。
  表面积计算包含所有外露面，包括内部孔洞的表面。

输入示例 1

4  
5  
0,0,0 0,0,1 0,0,2 0,0,3 0,0,4  
8  
0,0,0 0,0,1 0,1,0 0,1,1 1,0,0 1,0,1 1,1,0 1,1,1  
4  
0,0,0 0,0,1 1,1,0 1,1,1  
20  
0,0,0 0,0,1 0,0,2 0,1,2 0,2,2 0,2,1 0,2,0 0,1,0  
1,0,0 2,0,0 1,0,2 2,0,2 1,2,2 2,2,2 1,2,0 2,2,0  
2,1,0 2,1,2 2,0,1 2,2,1  

输出示例 1

1 22  
2 24  
3 NO 3  
4 72  

来源

Greater New York Regional 2008