Largest Uniform Square

You are given a grid with n rows and m columns filled with lowercase English letters. Your task is to find the side length of the largest square subgrid in which all the characters are the same.

One can solve this problem using dynamic programming. Let \(dp[i][j]\) be the side length of the largest uniform square whose bottom-right corner is at cell \((i, j)\). The recurrence relation is given by:

[ dp[i][j] = \begin{cases} 1, & \text{if } i = 0 \text{ or } j = 0 \ \min{dp[i-1][j],; dp[i][j-1],; dp[i-1][j-1]} + 1, & \text{if } grid[i][j] = grid[i-1][j] = grid[i][j-1] = grid[i-1][j-1] \ 1, & \text{otherwise} \end{cases} ]

The answer for a test case is the maximum value in the dp table.

inputFormat

The input is read from standard input. The first line contains an integer T, the number of test cases. Each test case is described as follows:

• The first line of each test case contains two integers n and m, representing the number of rows and columns.
• This is followed by n lines, each containing a string of m lowercase letters with no spaces.

outputFormat

For each test case, output a single integer on a separate line which indicates the side length of the largest uniform square subgrid.

## sample

3
3 4
aaaa
abaa
abbb
4 4
abcd
abcd
abcd
abcd
5 5
zzzzz
zzzzz
zzzzz
zzzzz
zzzzz

2
1
5

</p>