After losing a night of Mahjong, Xiao z and Xiao c uninstalled all card games from their phones. However, how could this possibly stop their determination to slack off in class? Now their eyes are set on board games, but apart from playing "Flying Chess" every day, they only have a rough understanding of the rules of almost all other board games.

"Since we both know how to play but only a little bit, why don't we create a 'Frankenstein' game ourselves?"

Thus, through their careful brainstorming, a wonderful game that fuses Go, Xiangqi, and Stratego was born...

Description

The game is played on a grid-shaped board with $n$ rows and $m$ columns, where pieces are placed on the intersections of the grid. Let the coordinates of the top-left intersection be $(1, 1)$ and the bottom-right intersection be $(n, m)$.

Pieces are either black or white, with each player controlling one color.

Each piece has a level in addition to its color. Let $col_i$ be the color of piece $i$, and $lv_i$ be the level of piece $i$. Additionally, there are 4 types of states for the grid lines on the board. For the $i$-th grid line, let its state be $opt_i$.

When it is a player's turn, they can choose one of their own pieces on the board and move it along the grid lines to another intersection, which is called a move. The process of a move is formally defined as follows: choose a sequence of coordinates $(x_0, y_0), (x_1, y_1), \dots, (x_k, y_k)$, where $k$ is any chosen positive integer, $(x_0, y_0)$ is the initial position of the piece, and $(x_k, y_k)$ is the final position of the piece. The following conditions must be met:

• For any $i = 0, 1, \dots, k - 1$, there must be a grid line directly connecting $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$, which means the move must follow the grid lines.
• For any $i \neq j$, we must have $(x_i, y_i) \neq (x_j, y_j)$, which means the piece cannot pass through the same position during the move. Specifically, $(x_0, y_0) \neq (x_k, y_k)$, which means the piece cannot stay in place (or return to the starting position).
• For any $i = 1, \dots, k - 1$, there must be no piece at $(x_i, y_i)$, which means the piece cannot jump over existing pieces during the move.
• If there is no piece at $(x_k, y_k)$, it is called a normal move; otherwise, it is called a capture. In a capture, let the color of the moving piece be $col_1$ and its level be $lv_1$, and the color of the captured piece be $col_2$ and its level be $lv_2$. It must satisfy $col_1 \neq col_2$ and $lv_1 \geq lv_2$. In other words, you can only capture a piece of a different color whose level is not higher than your own.

Note that it follows from the above definition that a piece is not allowed to continue moving after a capture.

The meanings of the grid line states are as follows:

• If $opt_i = 0$, it means the path is blocked, and the piece cannot pass through this grid line.
• If $opt_i = 1$, it means this grid line is a "normal road," and the piece can pass through at most 1 normal road in each move.
• If $opt_i = 2$, it means this grid line is a "straight road," and the piece can pass through any number of straight roads in each move, but it must move in a straight horizontal or vertical line and cannot turn. For example, moving from $(1, 1)$ through $(1, 2)$ to $(1, 3)$ along straight roads is allowed, but moving from $(1, 1)$ through $(1, 2)$ to $(2, 2)$ is not.
• If $opt_i = 3$, it means this grid line is an "interconnected road," and the piece can pass through any number of interconnected roads in each move, and can turn at will.

At the same time, it is stipulated that during a single move, the states of all grid lines passed by the piece must be the same. For example, moving from $(1, 1)$ through a straight road to $(1, 2)$ and then through an interconnected road to $(1, 3)$ is not allowed.

Details regarding how to determine the winner are irrelevant to this problem and are omitted.

After developing this board game, Xiao z and Xiao c came up with a training strategy to improve their skills: the board starts empty, and then Xiao c places a piece on an empty intersection each time. Xiao z needs to quickly calculate: if this newly placed piece is chosen to make a move, how many positions on the board can it reach? Note that because this is just mental training, they do not actually move the piece.

Poor Xiao z found that his calculation power was insufficient to solve this problem, so he had to ask you for help.

Input

The input is read from the file chess.in. Each test case consists of multiple data sets. The first line contains a positive integer $T$, representing the number of data sets. For each data set: The first line contains 3 positive integers $n, m, q$, representing the number of rows, columns, and the number of rounds of the game, respectively. The next $n$ lines, each containing a string of length $m - 1$, where each character is one of '0', '1', '2', '3'. The $j$-th character of the $i$-th line represents the state of the grid line connecting $(i, j)$ to $(i, j + 1)$. The next $n - 1$ lines, each containing a string of length $m$, where each character is one of '0', '1', '2', '3'. The $j$-th character of the $i$-th line represents the state of the grid line connecting $(i, j)$ to $(i + 1, j)$. The next $q$ lines, each containing 4 non-negative integers $col_i, lv_i, x_i, y_i$, representing that in the $i$-th round, a piece with color $col_i$ and level $lv_i$ is placed at intersection $(x_i, y_i)$. Here $col_i = 0$ represents a black piece, and $col_i = 1$ represents a white piece. It is guaranteed that there was no piece at intersection $(x_i, y_i)$ before.

Output

The output is written to the file chess.out. For each data set, output $q$ lines, each containing a non-negative integer representing the number of reachable intersections after the $i$-th piece is placed.

Examples

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

Output 1

4
3
3
3
2

Note 1

After placing piece 1, the reachable positions are $(2, 1), (2, 2), (3, 2), (3, 3)$. After placing piece 2, the reachable positions are $(2, 2), (2, 3), (3, 1)$. After placing piece 3, the reachable positions are $(1, 1), (1, 3), (2, 2)$. After placing piece 4, the reachable positions are $(2, 2), (3, 1), (3, 3)$. After placing piece 5, the reachable positions are $(2, 3), (3, 2)$.

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

Output 2

3
4
4
2
5
5
1

Constraints

For 100% of the data, $1 \leq T \leq 5$, $2 \leq n, m \leq 10^5$, $4 \leq n \times m \leq 2 \times 10^5$, $1 \leq q \leq \min\{10^5, n \times m\}$, $1 \leq lv_i \leq q$, $1 \leq x_i \leq n$, $1 \leq y_i \leq m$, $col_i \in \{0, 1\}$.

Note: Due to the large scale of input and output for this problem, it is recommended to use faster input/output methods.