B-CirnoNine 在梦里的画

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ CirnoNine 做了一个梦，在梦里她作了一幅美妙绝伦的画。但是她醒来后却忘记了梦的细节。她依稀记得她在梦中作出的画的形状，并确信自己是一笔就画成的天才，但她忘记了画笔的大小。

$\hspace{15pt}$ CirnoNine 看到一个由黑白方格构成的画面。她记得画面是由若干个大小相同的 $a\times a$ 全黑正方形拼成的（可以重叠）。假如每个 $a\times a$ 方块用其左上角的格子来标记，这些左上角坐标会沿着一条“路径”排列：路径是左上角坐标的序列，序列中相邻两点上下或左右相邻，这些 $a \times a$ 方块的并集恰好等于所有黑色格子。路径可能经过一个点多次。
$\hspace{15pt}$ 现在给你一个 $n \times m$ 的黑白网格，求满足上述条件的最大整数 $a$ （若不存在任何这样的 $a$ ，则输出 $0$ ）。

$\hspace{15pt}$ 形式化地说：
$\hspace{23pt}\bullet\,$ 给定一个 $n$ 行 $m$ 列、仅由 $0$ 和 $1$ 构成的矩阵 $A\left(\forall\ 1 \le i \le n;\, 1 \le j \le m;\, A_{i,j} \in \{0,1\}\right)$
$\hspace{23pt}\bullet\,$ 若位置 $(x,y)$ 满足 $1 \le x \le n−a+1$ 、 $1 \le y \le m−a+1$ ，且对于任意 $i,j$ 满足 $x \le i \le x+a-1$ 、 $y \le j \le y+a-1$ 都有 $A_{i,j}=1$ ，则称 $(x,y)$ 是一个合法位置。
$\hspace{23pt}\bullet\,$ 一条路径是长度为 $k\left(k \ge 1\right)$ 的合法位置序列 $P = (p_1, p_2, \cdots, p_k)$ ，其中每个位置 $p_i=(x_i,y_i)$ 都是合法位置，序列中的元素可以重复，并且对所有 $1 \le i < k$ 有 $|x_{i+1}−x_i|$ $+$ $|y_{i+1}−y_i| = 1$ 。
$\hspace{23pt}\bullet\,$ 对于任意合法位置 $q$ ，作为序列元素至少出现一次，即存在某个 $1\le i\le k$ 使得 $p_i=q$ 。
$\hspace{23pt}\bullet\,$ 若存在某个 $a \geq 1$ 和一条路径 $P$ ，使得路径上每个位置对应的 $a\times a$ 方块的并集恰好等于集合 $\{ (i,j) | A_{i,j} = 1 \}$ ，则称 $a$ 为可行的。
$\hspace{23pt}\bullet\,$ 你需要求出最大且可行的 $a$ （若不存在任何这样的 $a$ ，则输出 $0$ ）。
$\hspace{15pt}$ （有一只哆来咪在偷笑）

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入两个整数 ，表示矩阵的行数和列数。
此后  行，第  行输入一个长度为 ，仅由字符  和  构成的字符串 ，表示矩阵的第  行。其中，字符  表示第  行第  列是黑色的，字符  代表白色。数据保证画布上至少存在一个 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示最大可行的 （若不存在任何可行的 ，则输出 ）。

示例1

输入

复制

输出

复制

说明

对于第一组测试数据，黑格为 、、。当  时，把每个黑格看成一个  方块。可以取路径 ，相邻坐标曼哈顿距离均为 ，且三个  方块的并集恰好是矩阵中所有的 ，因此  可行。 

对于第二组测试数据，所有合法的  全  方块的左上角是 、、。它们可以按路径  串联，且它们对应的  方块覆盖的格子集合恰好是矩阵中所有的 ，因此  可行。 

对于第三组测试数据，可以证明无法一笔画完这幅图，不存在可行的 。

对于第四组测试数据，最大的可行的 。下面是作画过程，绿色为当前绘制的左上角格子，深蓝色为左上角格子形成的路径：



对于第五组测试数据，最大的可行的 。下面是作画过程，绿色为当前绘制的左上角格子，深蓝色为左上角格子形成的路径，浅蓝色为涂黑的正方形：

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。