# Breadth First Search

# Bitmap

Rectangular bitmap of size **n** * **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`

) and _{1}`p`

= (_{2}`i`

, _{2}`j`

) is defined as:_{2}

d(`p`

, _{1}`p`

) = |_{2}`i`

– _{1}`i`

| + |_{2}`j`

– _{1}`j`

|_{2}

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** ≤ **n** ≤ **1000**, **1** ≤ **m** ≤ **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** ≤ **i** ≤ **n**, **1** ≤ **j** ≤ **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.

1 3 4 0001 0011 0110

3 2 1 0 2 1 0 0 1 0 0 1