Бітова карта

Задано прямокутну бітову карту розміром $n\times m$. Кожна точка на цій карті може бути білою або чорною, причому хоча б одна точка обов'язково біла. Точку в $i$-му рядку та $j$-му стовпці назвемо пікселем $(i,j)$. Відстань між двома пікселями $p_1=(i_1,j_1)$ і $p_2=(i_2,j_2)$ визначається так:

Для кожної точки на карті знайдіть відстань до найближчої білої точки.

Вхідні дані

Перша строка містить кількість тестів $t$. Перша строка кожного тесту містить два цілі числа $n,m(1\le n\le 1000,1\le m\le 1000)$. Кожен з наступних $n$ рядків містить слово з нулів і одиниць довжини $m$, що описує бітову карту. На $j$-ій позиції $i$-го $(1\le i\le n,1\le j\le m)$ рядка знаходиться $1$, якщо точка $(i,j)$ біла.

Вихідні дані

Для кожного тесту виведіть $n$ рядків, кожен з яких містить $m$ цілих чисел $f(i,1),...,f(i,m)$, де $f(i,j)$ — це відстань від точки $(i,j)$ до найближчої білої точки.

Приклади