You have a rectangular grid of size N × M, namely, there are cells (x, y) for 1 = x = N, 1 = y = M. Two cells are adjacent if they share a side. More formally, two cells (x₁, y₁), (x₂, y₂) are adjacent if |x₁ - x₂| + |y₁ - y₂| = 1. Between two adjacent cells there can be a wall. Two cells a and b are connected if there is a way between them (in other words there is a sequence of cells c₁, c₂, ..., c_k that c₁ = a, c_k = b, and for each 1 = i , c_i, c_i+1 are adjacent cells without wall between them).

Now you are given Q queries, each of whom is of following four types.

• 1 x y - build the wall between cells (x, y) and (x, y+1). If there is already exist a wall between them, this query is ignored.
• 2 x y - build the wall between cells (x, y) and (x+1, y). If there is already exist a wall between them, this query is ignored.
• 3 x₁ y₁ x₂ y₂ - check if cells (x₁, y₁) and (x₂, y₂) are connected. You must answer 1 if they are connected, 0 otherwise.
• 4 - You must answer the size of the largest connected component. A connected component is a set of sells wherein each two cells are connected. The size of a connected component is a number of the cells in it.

You must assume that there are no walls on the grid before the queries.

Input

The first line of input contains an integer T, denoting the number of test cases. Then T test cases are follow.

The first line of each test case contains three space-separated integers N, M and Q, denoting the grid sizes and amount of queries. For next Q lines, each line contains a query. The format of queries are the same as described by the statement.

Output

For each test case, output an integer, denoting the sum of answers for queries of type 3 and 4. Note that you just print only the sum of the answers for each test case.

Constraints and Subtasks

• 1 = T = 100
• 2 = N, M = 1000
• The sum of Q over all test cases in one test file does not exceed 10⁶
• For queries of type 1: 1 = x = N and 1 = y = M-1
• For queries of type 2: 1 = x = N-1 and 1 = y = M
• For queries of type 3: 1 = x₁, x₂ = N and 1 = y₁, y₂ = M

Subtask 1: (15 points)

• 1 = Q × N × M = 10⁶

Subtask 2: (15 points)

• 1 = N, M = 300
• The sum of Q over all test cases in one test file does not exceed 10⁵

Subtask 3: (70 points)

• No additional constraints

Example

Explanation

Query 1. There are a lot of ways from (1,1) to (3,4). One of them is marked in red in the picture #1. So these are connected, then Answer = 1 in this query.

Query 2. In the picture #2 you can see the grid after second query.

Query 3. In the picture #3 you can see the grid after third query.

Query 4. In the picture #4 you can see the grid after fourth query.

Query 5. In the picture #5 the largest connected component marked in green. Thus Answer = 12.

Query 6. In the picture #6 you can see the grid after sixth query.

Query 7. In the picture #7 the largest connected component marked in green. Thus Answer = 7.

Query 8. As you can see in the picture #8, there are no ways from (1,1) to (3,4). So they are no longer connected, then Answer = 0.

Query 9. In the picture #9 you can see the grid after ninth query. There is no difference between it and the grid after the sixth query, because before the ninth query the wall was already built.

Query 10. When a = b, two cells a and b are always connected. Thus Answer = 1.

Therefore, the sum of the answers is 1 + 12 + 7 + 0 + 1 = 21, which you should print.