English

Given a table of squares with N rows and M columns, each square has a value of 1 or 2. The table of tiles can be moved in one of four Up-Down-Left-Right ways:

• Up: the lines move up 1 line, the top line moves to the bottom.
• Down: the lines move down 1 line, the bottom line moves to the top
• Left : the columns move to the left 1 column, the leftmost column moves to the right column.
• Right : the columns move to the right 1 column, the right column moves to the left most column.

Given T queries of one of four types:

• 1 x : execute x Down commands with the given table of squares.
• 2 x : execute x Right commands with the given table of squares.
• 3 x : execute x Up command with the given table of squares.
• 4 x : execute x Left commands with the given grid of squares.

For each query give the number of 2×2 squares whose sum is 4 or 8.

Input

The first line is the number of test cases T of the problem.

The first line of each test case is 3 numbers N, M, K. The number of rows, the number of columns of the matrix and the number of queries, respectively.

Next N lines, each containing M numbers (1, 2) indicating the value at position (i, j)

Next K lines, each line is a query in the above format.

Output

Each test case is printed on 1 line, starting with the character '#', followed by the test case number, followed by 1 space, and finally K results for each query. (Each result is separated by 1 space.)

Constraints

1 <= T <= 70

3 <= N, M <= 2000

1 <= K <= 10^5

1 <= x <= 10^9

Example

Input:
1
4 5 5
1 1 2 2 2
1 1 2 2 2
2 2 2 2 1
1 1 1 1 1
1 1
1 2
1 3
2 1
2 2

Output:
#1 5 4 2 3 2

Vietnamese

Cho một bảng ô vuông N hàng M cột, mỗi ô vuông có giá trị 1 hoặc 2. bảng ô vuông có thể dịch chuyển theo một trong bốn cách Up-Down-Left-Right:

• Up: các dòng dịch chuyển lên trên 1 dòng, dòng trên cùng dịch chuyển xuống dưới cùng.
• Down: các dòng dịch chuyển xuống dưới 1 dòng, dòng dưới cùng dịch chuyển lên trên cùng
• Left : các cột dịch chuyển sang trái 1 cột, cột tráu nhất dịch chuyển tới cột phải nhất.
• Right : các cột dịch chuyển sang phải 1 cột, cột phải nhất dịch chuyển tới cột trái nhất.

Cho T truy vấn thuộc một trong 4 loại:

• 1 x : thực hiện x lệnh Down với bảng ô vuông đã cho.
• 2 x : thực hiện x lệnh Right với bảng ô vuông đã cho.
3 x : thực hiện x lệnh Up với bảng ô vuông đã cho.
• 4 x : thực hiện x lệnh Left với bảng ô vuông đã cho.

Với mỗi truy vấn hãy đưa ra số ô vuông 2x2 có tổng bằng 4 hoặc 8. 

Input

Dòng đầu tiên là số testcase T của bài toán

Dòng đầu tiên của mỗi testcase là 3 số N, M, K. Lần lượt là số dòng, số cột của ma trận và số truy vấn 

N dòng tiếp theoi, mỗi dòng chứa M số (1, 2) cho biết giá trị tại vị trí (i, j)

K dòng tiếp theo, mỗi dòng là một truy vấn theo định dạng trên.

Output

Mỗi tescase được in trên 1 dòng, với băt đầu là ký tự '#', tiếp theo là số thứ tự của testcase, tiếp đến là 1 khoảng trắng (dấu cách), và cuối cùng là K kết quả của từng truy vấn (mỗi kết quả cách nhau bởi 1 dấu cách)

Giới hạn

1 <= T <= 70

3 <= N, M <= 2000

1<= K <= 10^5

1 <= x <= 10^9

Example

Input:
1
4 5 5
1 1 2 2 2
1 1 2 2 2
2 2 2 2 1
1 1 1 1 1
1 1
1 2
1 3
2 1
2 2

Output:
#1 5 4 2 3 2