Problem E: 数立方体(头顶标数法)

Problem E: 数立方体(头顶标数法)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 51  Solved: 7
[Submit] [Status] [Web Board] [Creator:]

Description

三维空间上有一个物体,该物体能被网格划分,即对于一个1*1*1的小立方体,要么恰好是该物体的一部分,要么不是。
该物体的所有小立方体都在一个n*n*n的大立方体中,物体的所有小立方体连通。
如果该物体的小立方体AB满足条件之一,就说小立方体AB是连通的:
(1)AB存在公共面
(2)AC连通,CB连通(C也是该物体的一个小立方体)
PIPI分别与Z平面平行、X平面平行、Y平面平行来观察这个物品,得到该物品的XY视图、YZ视图和ZX视图。
现在给出该物体的XY视图、YZ视图和ZX视图,这个物体体积最大可能是多少(即该物体所占的小立方体的个数)?
如果不存在一个物体能产生这样的三视图,输出-1
XY视图、YZ视图和ZX视图都是n*n的矩阵。
把空间的n*n*n个小立方体标号为(0,0,0),(0,0,1),...,(n-1,n-1,n-1)
XY[i][j]='Y',表示该视图处是实心的,即(i,j,0),(i,j,1),...,(i,j,n-1)中至少有一个小立方体属于该物体。
XY[i][j]='N',表示该视图处是空心的,即(i,j,0),(i,j,1),...,(i,j,n-1)中没有小立方体属于该物体。
YZ[i][j]='Y',表示该视图处是实心的,即(0,i,j),(1,i,j),...,(n-1,i,j)中至少有一个小立方体属于该物体。
YZ[i][j]='N',表示该视图处是空心的,即(0,i,j),(1,i,j),...,(n-1,i,j)中没有小立方体属于该物体。
ZX[i][j]='Y',表示该视图处是实心的,即(j,0,i),(j,1,i),...,(j,n-1,i)中至少有一个小立方体属于该物体。
ZX[i][j]='N',表示该视图处是空心的,即(j,0,i),(j,1,i),...,(j,n-1,i)中没有小立方体属于该物体。

Input

第一行一个整数T,表示测试用例的组数(1\le T\le 10) 
对于每组测试用例: 
第一行一个整数n(1\le n\le 10) 之后有3*n行,每行n个字符,每个字符是'Y''N'
n行表示XY视图,中间n行表示YZ视图,最后n行表示ZX视图,保证这3*n*n个字符中至少存在一个'Y' 

Output

输出T行,第i行一个整数为第i组测试用例的答案。 

Sample Input

2
2
YN
NN
YN
NN
YN
NN
2
YN
NY
YN
NY
YN
NY

Sample Output

1
-1