VONNY - Vonny and her dominos

Vonny loves playing with dominos. And so she owns a standard set of dominos. A standard set of dominos consists of 28 pieces called bones, tiles or stones. Each bone is a rectangular tile with a line dividing its face into two square ends. Each square is labeled with a number between 0 and 6. The 28 stones are labeled (0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (1, 1), (1, 2) ... (5, 5), (5, 6), (6, 6). Tommy - the brother of Vonny - build a box for Vonny's dominos. This box is sized 7 × 8 squares. Every square is labeled with a number between 0 and 6. You can see a example box here.

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

Now Vonny wants to arrange her 28 stones in such way that her stones cover all squares of the box. A stone can only be placed on two adjacent squares if the numbers of the squares and of the domino stone are equal. Tommy asks Vonny in how many different ways she can arrange the dominos. Tommy assumes that Vonny need a lot of time to answer the question. And so he can take some of Vonny's candies while she solves the task. But Vonny is a smart and clever girl. She asks you to solve the task and keeps an eye on her candies.

Input

The first line of the input contains the number of testcases. Each case consists of 56 numbers (7 rows and 8 cols) between 0 and 6 which represents Tommy's box.

Output

For each testcase output a single line with the number which answers Tommy's question.

Example

Input:
2
0 3 0 2 2 0 2 3 
1 5 6 5 5 1 2 2 
3 4 1 4 5 4 4 4 
6 6 1 0 5 2 3 0 
4 0 3 2 4 1 6 0 
1 4 1 5 6 6 3 0 
1 2 6 5 5 6 3 3 

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

Output:
18
1

Added by:Simon
Date:2004-10-18
Time limit:20s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET

hide comments
2022-06-30 12:21:10
1 DAM AC
2017-09-01 18:25:08
Ac in one go!
Testcase 2 get answer is 2 not 1
2016-03-29 17:26:45
getting correct answer for given TC but WA at submission
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.