Migrated from Lutece 141 A famous problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

The eight-puzzle is a famous problem which consists of eight sliding tiles, numbered by digits from $1$ to $8$, placed in a $3\times 3$ squared board of nine cells.

One of the cells is always empty, in each step, any adjacent (horizontally and vertically) tile can be moved into the empty cell, so that we can change the board's state from one to another.

We say two states'distance is the minimum steps you need to change a state into another. And we say two states are the same if and only if all the elements in the nine cells are corresponsive same, so the distance with the same states is $0$.

So now, your mission comes, give you an initial state,and a number $D$, you have to find how many different states that has the distance of $D$ from the initial state.

Input

In the first line, you will get a number $T$ denote the number of the test cases. ($1\leq T\leq 1000$)

Follow are the $T$ cases

Each of the first $3$ lines of each case contains $3$ numbers, so the $3\times 3$ matrix denote the initial state.

The $4_{th}$ line contains a number $M$ ($1\leq M\leq 1000$) denotes the number of queries in this test case.

The next $M$ lines, each contains a number denotes $D$ ($0\leq D\leq 9!$) as described above.

Output

For each query, you should output a line with a number denotes the number of different states that has the distance of $D$ from the initial state.

Samples

2
0 1 2
3 4 5
6 7 8
2
1
2
1 2 3
4 0 5
6 7 8
1
1

2
4
4

Note

Huge input, please use scanf/printf instead of cin/cout

Resources

Sichuan State Programming Contest 2008