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:

For each pixel find the distance to the nearest white pixel.

Input

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.

Output

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.

Examples