UCUBE - The Unstable Cube

no tags 

A large cube (of size NxNxN) is given. At the beginning it consists of small blocks (1x1x1) and each block is painted in some color (different blocks may have the same color). But in the process of exploitation some blocks have disappeared. Given 6 photos of the unstable cube you have to calculate the maximum possible number of blocks that still remain in the unstable cube. It is possible that the unstable cube consists of more than one part.

Input

t – the number of test cases, then t test cases follow.
N - size of the big cube [1 <= N <= 10]
In the next N lines views of the cube from 6 sides are described (in the following order: from the front, left, back, right, from above, from below). Each such view is represented by a table of size NxN in which different letters denote different colors, and the symbol "." (point) means that it is possible to see all the way through the cube at this point. Consecutive views are separated by exactly one space.

The bottom border of the top view corresponds to the top border of the front view, and the top border of the bottom view - to the bottom border of the front view. For the front, back, left and right views the top and bottom sides of a view correspond to the top and bottom of the cube.

The input file is correct, i.e. each test case describes a possible configuration.

Output

For each test case output one integer: the required maximum number of blocks remaining in the unstable cube.

Example

Input:
2
3
.R. YYR .Y. RYY .Y. .R.
GRB YGR BYG RBY GYB GRB
.R. YRR .Y. RRY .R. .Y.
2
ZZ ZZ ZZ ZZ ZZ ZZ
ZZ ZZ ZZ ZZ ZZ ZZ

Output:
11
8

hide comments
:D: 2009-08-13 21:45:52

The letters are all upper case.

Last edit: 2009-08-14 07:59:25

Added by:Roman Sol
Date:2005-03-01
Time limit:1s
Source limit:20000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:The Moscow Olympiad on computer science 2004/05. Correspondence round.