Problems
Bitmap
Bitmap
Rectangular bitmap of size $n \times m$ is given. Each pixel of the bitmap is either white or black, but at least one is white. The pixel in $i$-th line and $j$-th column is called the pixel $(i, j)$. The distance between two pixels $p_1 = (i_1, j_1)$ and $p_2 = (i_2, j_2)$ is defined as:
$$
d(p_1, p_2) = |i_1~–~i_2| + |j_1~–~j_2|
$$
For each pixel find the distance to the nearest white pixel.
\InputFile
The number of test cases $t$ is given in the first line, then $t$ test cases follow. First line of each test case contains pair of integer numbers $n, m~(1 \le n \le 1000, 1 \le m \le 1000)$. In each of the following $n$ lines of the test case exactly one zero-one word of length $m$, the description of one line of the bitmap, is written. On the $j$-th position in the line $i~(1 \le i \le n, 1 \le j \le m)$ there is $1$ if, and only if the pixel $(i, j)$ is white.
\OutputFile
In the $i$-th line for each test case there should be written $m$ integers $f(i, 1), ..., f(i, m)$ separated by single spaces, where $f(i, j)$ is the distance from the pixel $(i, j)$ to the nearest white pixel.
Input example #1
1 3 4 0001 0011 0110
Output example #1
3 2 1 0 2 1 0 0 1 0 0 1