Problem:


Nets of Dice

In mathematics, some plain words have special meanings.
The word "net" is one of such technical terms.
In mathematics, the word "net" is sometimes used to
mean a plane shape 
which can be folded into some solid shape.

The following are a solid shape (Figure 1) and one of its net (Figure 2).

Figure 1: a prismFigure 2: a net of a prism

Nets corresponding to a solid shape are not unique.
For example, Figure 3 shows three of the nets of a cube.

Figure 3: examples of nets of a cube

In this problem, we consider nets of dice.
The definition of a die is as follows.

 A die is a cube, each face marked with a number between one and six.

 Numbers on faces of a die are different from each other.

 The sum of two numbers on the opposite faces is always 7.

Usually, a die is used in pair with another die.
The plural form of the word "die" is "dice".

Some examples of proper nets of dice are shown in Figure 4,
and those of improper ones are shown in Figure 5.

Figure 4: examples of proper nets of dice

Figure 5: examples of improper nets

The reasons why each example in Figure 5 is improper are as follows.

(a) The sum of two numbers on the opposite faces is not always 7.
(b) Some faces are marked with the same number.
(c) This is not a net of a cube. Some faces overlap each other.
(d) This is not a net of a cube.
Some faces overlap each other and one face of a cube is not covered.
(e) This is not a net of a cube. 
The plane shape is cut off into two parts.
The face marked with '2' is isolated.
(f) This is not a net of a cube.
The plane shape is cut off into two parts.
(g) There is an extra face marked with '5'.

Notice that there are two kinds of dice.
For example, the solid shapes formed from 
the first two examples in Figure 4 
are mirror images of each other.

Any net of a die can be expressed on a sheet of 5x5 mesh like the one in Figure 6.
In the figure, gray squares are the parts to be cut off.
When we represent the sheet of mesh by numbers as in Figure 7,
squares cut off are marked with zeros.

Figure 6: 5x5 meshFigure 7: representation by numbers

Your job is to write a program which tells
the proper nets of a die from the improper ones automatically.

Input

The input consists of multiple sheets of 5x5 mesh.

N

Mesh0

Mesh1

...

MeshN-1

N is the number of sheets of mesh.
Each Meshi gives a sheet of mesh
on which a net of a die is expressed.
Meshi is in the following format.

        F00
	F01
	F02
	F03
	F04

  
	F10
	F11
	F12
	F13
	F14

  
	F20
	F21
	F22
	F23
	F24

  
	F30
	F31
	F32
	F33
	F34

  
	F40
	F41
	F42
	F43
	F44

Each Fij is an integer between 0 and 6.
They are separated by a space character.

Output

For each Meshi, 
the truth value, true or false, 
should be output, each in a separate line.
When the net of a die expressed on the Meshi is proper, 
output "true".
Otherwise, output "false".

Sample Input

6
0 0 0 0 0
0 0 0 0 6
0 2 4 5 3
0 0 1 0 0
0 0 0 0 0
0 0 3 0 0
0 0 2 0 0
0 0 4 1 0
0 0 0 5 0
0 0 0 6 0
0 0 0 3 0
0 0 2 5 0
0 4 1 0 0
0 0 6 0 0
0 0 0 0 0
0 6 2 0 0
0 0 4 0 0
0 1 5 0 0
0 0 3 0 0
0 0 0 0 0
0 0 0 0 6
0 2 4 5 3
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 0 6
0 2 4 5 3
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0

Output for the Sample Input

true
true
false
false
false
false



Sample input:
6
0 0 0 0 0
0 0 0 0 6
0 2 4 5 3
0 0 1 0 0
0 0 0 0 0
0 0 3 0 0
0 0 2 0 0
0 0 4 1 0
0 0 0 5 0
0 0 0 6 0
0 0 0 3 0
0 0 2 5 0
0 4 1 0 0
0 0 6 0 0
0 0 0 0 0
0 6 2 0 0
0 0 4 0 0
0 1 5 0 0
0 0 3 0 0
0 0 0 0 0
0 0 0 0 6
0 2 4 5 3
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 0 6
0 2 4 5 3
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0


Sample output:
true
true
false
false
false
false

Submission status: Wrong Answer

Solution code:
import copy

def op(v1,v2):
    vr=(v1[1]*v2[2]-v1[2]*v2[1], v1[2]*v2[0]-v1[0]*v2[2],  v1[0]*v2[1]-v1[1]*v2[0])
    if vr==(0,0,0):
        return v1
    else:
        return vr

class Dice:
    def __init__(self):
        self.vlist=[(1,0,0),(-1,0,0),(0,1,0),(0,-1,0),(0,0,1),(0,0,-1)]
        self.face={}
        self.nums=[]
        for i in (-1,1):
            self.face[(i,0,0)]=0
            self.face[(0,i,0)]=0
            self.face[(0,0,i)]=0
    def rotate(self,v2):
        Nd=copy.deepcopy(self.face)
        for v in self.vlist:
            nv=op(v,v2)
            Nd[nv]=self.face[v]
        self.face=copy.deepcopy(Nd)
        #self.top=op(self.top,v2)
    def fill(self,n):
        self.face[(1,0,0)]=n
        self.nums.append(n)
    def check(self):
        ans=1
        if len(self.nums)!=6:
            ans=0
        else:
            for i in range(1,7):
                if i not in self.nums:
                    ans=0
            if (self.face[(-1,0,0)]+self.face[(1,0,0)]!=7 or self.face[(0,-1,0)]+self.face[(0,1,0)]!=7 or self.face[(0,0,-1)]+self.face[(0,0,1)]!=7):
                ans=0
        return ans
        
def fd(D,A,i,j):
    if A[i][j]!=0:
        D.fill(A[i][j])
        dt=D.vlist
        A[i][j]=0
        if A[i-1][j]!=0:
            D.rotate((0,-1,0))
            fd(D,A,i-1,j)
        if A[i+1][j]!=0:
            D.rotate((0,1,0))
            fd(D,A,i+1,j)    
        if A[i][j-1]!=0:
            D.rotate((0,0,1))
            fd(D,A,i,j-1)
        if A[i][j+1]!=0:
            D.rotate((0,0,-1))
            fd(D,A,i,j+1)
        D.vlist=dt

    
N=int(raw_input())
for p in range(N):
    A=[[0 for i in range(7)] for j in range(7)]
    D=Dice()
    for i in range(1,6):
        A[i][1:6]=[int(x) for x in raw_input().split()]
    for i in range(7):
        for j in range(7):
            if A[i][j]!=0:
                fd(D,A,i,j)
    if D.check():
        print 'true'
    else:
        print 'false'