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 x 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