Bit xəritəsi

Verilmiş düzbucaqlı bit xəritəsi $n\times m$ ölçüsündədir. Hər bir nöqtə ya ağ, ya da qaradır və ən azı bir nöqtə ağdır. $i$-ci sırada və $j$-ci sütunda yerləşən nöqtəni $(i,j)$ pikseli adlandıraq. $p_1=(i_1,j_1)$ və $p_2=(i_2,j_2)$ pikselləri arasındakı məsafə aşağıdakı kimi müəyyən edilir:

Hər bir nöqtə üçün ən yaxın ağ nöqtəyə olan məsafəni tapın.

Giriş verilənləri

Birinci sətir testlərin sayını $t$ ehtiva edir. Hər bir testin birinci sətiri iki tam ədəd $n,m(1\le n\le 1000,1\le m\le 1000)$ ehtiva edir. Sonrakı $n$ sətirin hər biri uzunluğu $m$ olan sıfır və birlərdən ibarət bir söz ehtiva edir, bit xəritəsini təsvir edir. $j$-ci mövqedə $i(1\le i\le n,1\le j\le m)$-ci sırada yalnız nöqtə $(i,j)$ ağdırsa $1$ var.

Çıxış verilənləri

Hər bir test üçün $i$-ci sırada $m$ tam ədəd $f(i,1),...,f(i,m)$ çıxarın, burada $f(i,j)$ nöqtə $(i,j)$-dən ən yaxın ağ nöqtəyə olan məsafədir.

Nümunələr