You are given a rectangular field whose dimensions are . The field is split into different cells. The cell on the row and column has a constant height of .
Now, you wish to build a pyramid somewhere in the field. Formally, a pyramid of size is a square where the cell at the row and column has a constant height of . For example, here are pyramids of sizes from to :
To build a pyramid, you have blocks whose dimensions are . You can increase the height of any cell by by placing a single block on that cell. However, you can't reduce the height of any cell. You also can't change the height of any region outside the field.
What is the largest pyramid that you can form? Note that you don't have to use all of the blocks.
Input Format
The first line of input contains a single integer denoting the number of queries.
The first line of each query contains three space-separated integers , and .
The next lines describe the field. The number in the line represents .
Constraints
Subtasks
- For of the maximum points,
Output Format
For each query, print a single line containing a single integer denoting the size of the maximum pyramid you can build. If it's impossible to build any pyramid, print .
Sample Input 0
5
3 3 1000
0 0 0
0 0 0
0 0 0
3 3 9
0 0 0
0 0 0
0 0 0
3 5 20
0 0 0 0 0
0 3 3 3 0
0 0 0 0 0
6 6 9
0 1 1 1 1 1
1 1 1 1 1 3
1 1 1 1 1 1
1 1 1 2 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1
2
Sample Output 0
2
1
1
3
0
Explanation 0
Query 1:
Here, we used blocks. The answer is .
Query 2:
We can't build a pyramid of size because there aren't enough blocks. But we can build a pyramid of size , so the answer is .
Query 3:
We can't build a pyramid of size because we can't decrease the height of any cell. Thus, the answer is .
Query 4:
Exactly 9 blocks are used and the size of the pyramid is .
Query 5:
It's not possible to build any pyramid, so the answer is .