A game is performed on a board with ~n~ rows and ~m~ columns. The pieces are placed on the intersections. Let the upper left corner be ~(1, 1)~ and the lower right corner be ~(n, m)~.

Two players respectively use black pieces and white pieces.

Each piece has a color and a level. Let ~col_i~ be the color of piece ~i~ and let ~lv_i~ be the level of piece ~i~. Also, an edge on the board has one of the ~4~ states explained later. The state of the ~i~-th edge is ~opt_i~.

In a player's turn, he can choose any of his own pieces and move that piece along the edges to another intersection. This is called a move. Formally, a move is the following process: Choose a sequence of coordinates ~(x_0, y_0), (x_1, y_1), \dots, (x_k, y_k)~ where ~k~ is a positive integer at the player's choice, ~(x_0, y_0)~ is the initial position of the piece, ~(x_k, y_k)~ is the final position the piece reaches, satisfying:

• For any ~i = 0, 1, \dots, k-1~, ~(x_i, y_i)~ and ~(x_{i+1}, y_{i+1})~ must be connected directly by an edge. In other words, players must move the pieces along the edges.
• For any ~i \ne j~, we must have ~(x_i, y_i) \ne (x_j, y_j)~. In other words, a piece cannot pass through the same intersection twice. In particular, ~(x_0, y_0) \ne (x_k, y_k)~, or in other words, it is not possible to stay at the origin or return to the origin.
• For any ~i = 1, \dots, k-1~, there cannot be any piece on ~(x_i, y_i)~. In other words, in a move a piece cannot pass through pieces that are already present.
• If there are no pieces on ~(x_k, y_k)~, we say the move is a normal move. Otherwise, we say it is a capture. In a capture, assume the piece that is currently being moved has color ~col_1~ and level ~lv_1~, and the piece that is going to be captured has color ~col_2~ and level ~lv_2~, then we must have ~col_1 \ne col_2~ and ~lv_1 \ge lv_2~. In other words, we can only capture a piece that has a different color and has a level that is no greater than the piece being moved.
• It shall be noted that by the above definition, moving the piece after a capture is not allowed.

The states of an edge are described below:

• If ~opt_i = 0~, then the edge is not accessible. It is not possible to move through the edge in a move.
• If ~opt_i = 1~, then the edge is a normal edge. In each move, a piece can pass through at most one normal edge.
• If ~opt_i = 2~, then the edge is a no-turn edge. In each move, the piece can pass through an arbitrary number of no-turn edges, but the piece can only move horizontally or vertically and the piece cannot make a turn. So for example, it is possible to move along a non-turn edge to go from ~(1,1)~ to ~(1,3)~ via ~(1,2)~, but it is not possible to move along a non-turn edge to go from ~(1,1)~ to ~(2,2)~ via ~(1,2)~.
• If ~opt_i = 3~, then the edge is an interchange edge. In each move, a piece can move through an arbitrary number of interchange edges, and it is possible to take turns.
• Finally, in a move, the states of all the edges a piece goes through must be the same. So for example, it is not possible to start from ~(1,1)~, go to ~(1,2)~ via a no-turn edge, and go to ~(1,3)~ via an interchange edge.

Now initially, the chessboard is empty. In each turn, a piece will be put at some empty intersection of the chessboard, and you need to compute how many intersections on the chessboard are accessible if we move the new piece. Please note that the piece will not be actually moved.

Input Specification

Each test set has multiple test cases.

In the first line, there is a positive integer ~T~ denoting the number of test cases.

For each test case,

• In the first line, there are three positive integers ~n,m,q~ denoting the number of rows, the number of columns, and the number of rounds.
• In the following ~n~ lines, each line contains a string of length ~m-1~. Each character in the string is one from ~0, 1, 2, 3~. The ~j~-th character on the ~i~-th line denotes the state of the edge from intersection ~(i,j)~ to intersection ~(i,j+1)~.
• In the following ~n-1~ lines, each line contains a string of length ~m~. Each character in the string is one from ~0, 1, 2, 3~, and the ~j~-th character on the ~i~-th line denotes the state of the edge from intersection ~(i,j)~ to intersection ~(i+1,j)~.
• In the following ~q~ lines, each line has 4 non-negative integers ~col_i,lv_i,x_i,y_i~, denoting in round ~i~, there is a piece with color ~col_i~ and level ~lv_i~ that is put at intersection ~(x_i,y_i)~. ~col_i = 0~ denotes the piece is black, ~col_i = 1~ denotes the piece is white. It is guaranteed that before this round there are no pieces at intersection ~(x_i,y_i)~.

Output Specification

For each test case, output ~q~ lines with a non-negative integer on each line denoting the number of intersections that can be reached by the ~i~-th piece on the chessboard.

Sample Input 1

1
3 3 5
13
22
23
010
233
0 1 2 3
1 2 2 1
1 3 1 2
0 2 3 2
1 3 2 2

Sample Output 1

4
3
3
3
2

Explanation for Sample 1

The intersections piece 1 can reach are ~(2,1), (2,2), (3,2), (3,3)~.

The intersections piece 2 can reach are ~(2,2), (2,3), (3,1)~.

The intersections piece 3 can reach are ~(1,1), (1,3), (2,2)~.

The intersections piece 4 can reach are ~(2,2), (3,1), (3,3)~.

The intersections piece 5 can reach are ~(2,3), (3,2)~.

Sample Input 2

2
2 3 4
22
33
123
0 2 1 2
0 1 2 1
1 2 1 3
0 3 2 2
3 2 3
3
1
3
32
32
0 2 1 2
1 2 3 2
0 1 2 2

Sample Output 2

3
4
4
2
5
5
1

Additional Samples

Additional samples can be found here.

Constraints

For all test data, ~1 \le T \le 5~, ~2 \le n,m \le 10^5~, ~4 \le n \times m \le 2 \times 10^5~, ~1 \le q \le \min\{10^5, nm\}~, ~1 \le lv_i \le q~, ~1 \le x_i \le n~, ~1 \le y_i \le m~, ~col_i \in \{0,1\}~.

Test case	~n \times m \le~	~q \le~	Special properties
1-2	~100~	~50~	N/A
3-6	~5\,000~	~2\,000~
7-8	~2 \times 10^5~	~2 \times 10^5~	No no-turn edges or interchange edges
9-11			No interchange edges
12-14			No no-turn edges
15-16			~lv_i = i~
17-18			~lv_i = q-i+1~
19-21		~2\,000~	~n, m \le 1\,000~
22-25		~10^5~	N/A

Since the input is large, using efficient I/O methods is recommended.