Dice Puzzle#3200

Dice Puzzle

1 second

64 megabytes

Easy

Let's try a dice puzzle. The rules of this puzzle are as follows.

1. Dice with six faces as shown in Figure 1 are used in the puzzle.

Figure 1. Faces of a die

2. With twenty-seven such dice, a $3 \times 3 \times 3$ 3 \times 3 \times 3 cube is built as shown in Figure 2.

Figure 2. $3 \times 3 \times 3$ 3 \times 3 \times 3 cube

3. When building the cube, the sum of the numbers marked on the faces of adjacent dice that are placed against each other must be $7$ (see Figure 3). For example, if one face of the pair is marked $2$ , then the other face must be $5$ .

Figure 3. A pair of faces placed against each other

4. The top and front views of the cube are partially given, i.e., the numbers on faces of some of the dice on the top and on the front are known.

Figure 4. Top and front views of the cube

5. The goal of the puzzle is to find all possible dice arrangements consistent with the given top and front view information.

Your job is to write a program that solves this puzzle.

Input

The input consists of multiple datasets in the following format:

$N$

$D a t a se t_{1}$ Dataset_1

$D a t a se t_{2}$ Dataset_2

$\dots$

$D a t a se t_{N}$ Dataset_N

$N$ is the number of datasets.

The format of each dataset is as follows:

$T_{11}$ T_{11} $T_{12}$ T_{12} $T_{13}$ T_{13}

$T_{21}$ T_{21} $T_{22}$ T_{22} $T_{23}$ T_{23}

$T_{31}$ T_{31} $T_{32}$ T_{32} $T_{33}$ T_{33}

$F_{11}$ F_{11} $F_{12}$ F_{12} $F_{13}$ F_{13}

$F_{21}$ F_{21} $F_{22}$ F_{22} $F_{23}$ F_{23}

$F_{31}$ F_{31} $F_{32}$ F_{32} $F_{33}$ F_{33}

$T_{ij}$ T_{ij} and $F_{ij}$ F_{ij} ( $1 \leq i \leq 3$ 1 \leq i \leq 3, $1 \leq j \leq 3$ 1 \leq j \leq 3) are the faces of dice visible in the top and front views, as shown in Figure 6, or zero. Zero means the face at the corresponding position is unknown.

Output

For each possible arrangement of dice, compute the sum of the numbers marked on the nine faces visible on the right side of the cube, that is, with the notation given in Figure 2,

For each dataset, you should output the right view sums for all possible arrangements, in ascending order and without duplicates. Numbers should be separated by a single space.

When there are no possible arrangements for a dataset, output $0$ .

For example, suppose the top and front views are given as follows.

Figure 5.

There are four possible right views, as shown in Figure 6. The right view sums are $33$ , $36$ , $32$ , and $33$ , respectively. After putting them in ascending order and removing duplicates, the answer should be $323336$ .

The output should be one line for each dataset. The output may have spaces at the ends of lines.

Figure 6.

Examples

Example 1