该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Muxue youth discovers a series of ancient stone tablets in the snowfield ruins, each engraved with a mysterious binary number. These tablets are arranged according to some pattern, forming a massive binary matrix.

According to murals found in the ruins, these tablets are part of an ancient encryption system. To decode the cipher, one must find all the "perfect binary squares" in the matrix—square submatrices whose four corner digits satisfy a specific XOR relationship.

Problem Description

Given an $n \times m$ binary matrix $A$, where each element is either 0 or 1, define a perfect binary square as a square submatrix that satisfies the following conditions:

Let the side length of the square be $k$ ($k \geq 2$), and let its top-left corner coordinates be $(i, j)$. Then the four corner coordinates are:

• Top-left: $(i, j)$
• Top-right: $(i, j + k - 1)$
• Bottom-left: $(i + k - 1, j)$
• Bottom-right: $(i + k - 1, j + k - 1)$

Condition: The values $a, b, c, d$ at these four positions must satisfy:

$(a \oplus b) \oplus (c \oplus d) = 1$

where $\oplus$ denotes the XOR operation.

You need to answer $q$ queries. Each query specifies a rectangular region $[x_1, y_1, x_2, y_2]$ and asks how many perfect binary squares are fully contained within this region (i.e., all points of the square lie within the query region).

Input Format

The input contains multiple test cases. The first line contains an integer $T$ ($1 \leq T \leq 10$), indicating the number of test cases.

The format for each test case is as follows:

1. The first line contains three integers $n, m, q$ ($1 \leq n, m \leq 1000$, $1 \leq q \leq 10^5$)
2. The next $n$ lines each contain a string of length $m$, representing the binary matrix. The $j$-th character of the $i$-th line denotes $A_{i,j}$ ('0' or '1')
3. The next $q$ lines each contain four integers $x_1, y_1, x_2, y_2$ ($1 \leq x_1 \leq x_2 \leq n$, $1 \leq y_1 \leq y_2 \leq m$), representing a query

Output Format

For each query, output a single integer on a line, indicating the number of perfect binary squares within the region.

Sample Input

1
4 4 3
0101
1010
0101
1010
1 1 4 4
1 1 3 3
2 2 4 4

Sample Output

0
0
0

Explanation

Sample Explanation

Matrix:

0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

Perfect binary square condition: $(a \oplus b) \oplus (c \oplus d) = 1$

Query 1: Entire matrix

• Squares with side length 2:
  • (1,1): 0,1,1,0 → (0⊕1)⊕(1⊕0)=1⊕1=0
  • (1,2): 1,0,0,1 → 1⊕1=0
  • (1,3): 0,1,1,0 → 0
  • (2,1): 1,0,0,1 → 0
  • (2,2): 0,1,1,0 → 0
  • (2,3): 1,0,0,1 → 0
• Squares with side length 3:
  • (1,1): 0,0,0,0 → 0
  • (1,2): 1,1,1,1 → 0
  • (2,1): 1,1,1,1 → 0
  • (2,2): 0,0,0,0 → 0
• Squares with side length 4:
  • (1,1): 0,1,1,0 → 0

The condition can be simplified as: $a \oplus b \oplus c \oplus d = 1$

Note: The sample output may be based on other matrices satisfying the condition. In actual tests, ensure the correct test data is used.

Global Constraints

For all data:

• $1 \leq T \leq 10$
• The total sum of $n \times m$ across all test cases does not exceed $2 \times 10^6$
• The total sum of $q$ across all test cases does not exceed $2 \times 10^5$
• Matrix elements are only '0' or '1'

Subtasks

• Subtask 1 (20 points): $n, m \leq 50$, $q \leq 100$
• Subtask 2 (30 points): $n, m \leq 200$, $q \leq 1000$
• Subtask 3 (30 points): $n, m \leq 500$, $q \leq 5000$
• Subtask 4 (20 points): No additional restrictions