Coco has a $3 \times 3$ square grid-shaped chocolate container. This container has a blocked center cell with a screen attached to it that displays numbers. The remaining 8 cells can each hold at most one chocolate.

The screen displays up to 4 numbers, where each number represents the size of a connected component of cells containing chocolates. If there are multiple numbers, they are displayed in ascending order. Two cells are considered connected if they share a common side.

Coco wants to make another identical chocolate container to give to Hanbyeol as a gift. Help Coco test the container to ensure there are no bugs.

Input

The first line contains the number of test cases $T$ ($1 \le T \le 100$).

Each test case consists of 4 lines. The first 3 lines describe the state of the chocolate container. O indicates that there is a chocolate in that cell, X indicates there is none, and the center cell is marked as -. The 4th line contains the number of digits displayed on the screen $n$, followed by the list of numbers $a_1, a_2, \cdots, a_n$ in order ($0 \le n \le 4$, $1 \le a_1 \le a_2 \le \cdots \le a_n \le 8$).

Output

For each test case, output 1 if the display on the screen is correct, and 0 otherwise.

Examples

Input 1

6
OOO
O-O
XOO
1 7
XOO
O-O
XXO
2 1 4
OXO
O-X
XXO
3 1 1 2
XOX
O-O
XOX
4 1 1 1 1
XOO
O-O
OOX
1 6
OXX
O-O
XXO
3 1 1 2

Output 1

1
1
1
1
0
0