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.
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 .
For of the maximum points,
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 .