#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <time.h>
#include <queue>
#define mod 1000000000
#define ll long long int
using namespace std;
class point
{
public:
int x, y, z;
point(int i, int j, int k)
{
x = i;
y = j;
z = k;
}
};
int n, m;
int grid[200][200];
char board[200][200];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int iterations;
void BFS(queue <point> bfs)
{
int i, j, x, y;
point temp(0,0,0);
while(!bfs.empty())
{
temp = bfs.front();
bfs.pop();
grid[temp.x][temp.y] = temp.z;
// if the adjacent cells are unvisited, pushing it onto the queue.
for(i=0; i<4; i++)
{
iterations++;
x = temp.x+dx[i];
y = temp.y+dy[i];
if(grid[x][y]==-1)
bfs.push(point(x,y,temp.z+1));
}
}
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
printf("%d ", grid[i][j]);
printf("\n");
}
cout << "number of iterations : " << iterations << endl;
}
int main()
{
int t, i, j;
scanf("%d", &t);
while(t--)
{
queue <point> bfs;
// taking input
scanf("%d %d", &n, &m);
for(i=0; i<n; i++)
scanf("%s", board[i]);
// putting the value for each point to be -1
for(i=0; i<n; i++)
for(j=0; j<m; j++)
grid[i][j] = -1;
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
// if the point is white, putting its value to be 1, and pushing it onto the queue
if(board[i][j]=='1')
{
grid[i][j] = 0;
bfs.push(point(i,j,0));
}
}
}
iterations=0;
BFS(bfs);
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8dGltZS5oPgojaW5jbHVkZSA8cXVldWU+CiNkZWZpbmUgbW9kIDEwMDAwMDAwMDAKI2RlZmluZSBsbCBsb25nIGxvbmcgaW50CiAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIApjbGFzcyBwb2ludAp7CiAgICBwdWJsaWM6CiAgICAgICAgaW50IHgsIHksIHo7CiAgICBwb2ludChpbnQgaSwgaW50IGosIGludCBrKQogICAgewogICAgICAgIHggPSBpOwogICAgICAgIHkgPSBqOwogICAgICAgIHogPSBrOwogICAgfQp9OwogCmludCBuLCBtOwppbnQgZ3JpZFsyMDBdWzIwMF07CmNoYXIgYm9hcmRbMjAwXVsyMDBdOwogCmludCBkeFtdID0gezEsIC0xLCAwLCAwfTsKaW50IGR5W10gPSB7MCwgMCwgMSwgLTF9OwppbnQgaXRlcmF0aW9uczsKCnZvaWQgQkZTKHF1ZXVlIDxwb2ludD4gYmZzKQp7CiAgICBpbnQgaSwgaiwgeCwgeTsKICAgIHBvaW50IHRlbXAoMCwwLDApOwogICAgd2hpbGUoIWJmcy5lbXB0eSgpKQogICAgewogICAgICAgIHRlbXAgPSBiZnMuZnJvbnQoKTsKICAgICAgICBiZnMucG9wKCk7CiAgICAgICAgZ3JpZFt0ZW1wLnhdW3RlbXAueV0gPSB0ZW1wLno7CiAKCQkvLyBpZiB0aGUgYWRqYWNlbnQgY2VsbHMgYXJlIHVudmlzaXRlZCwgcHVzaGluZyBpdCBvbnRvIHRoZSBxdWV1ZS4KICAgICAgICBmb3IoaT0wOyBpPDQ7IGkrKykKICAgICAgICB7CgkJCWl0ZXJhdGlvbnMrKzsKICAgICAgICAgICAgeCA9IHRlbXAueCtkeFtpXTsKICAgICAgICAgICAgeSA9IHRlbXAueStkeVtpXTsKICAgICAgICAgICAgaWYoZ3JpZFt4XVt5XT09LTEpCiAgICAgICAgICAgICAgICBiZnMucHVzaChwb2ludCh4LHksdGVtcC56KzEpKTsKICAgICAgICB9CiAgICB9CiAgICBmb3IoaT0wOyBpPG47IGkrKykKICAgIHsKICAgICAgICBmb3Ioaj0wOyBqPG07IGorKykKICAgICAgICAgICAgcHJpbnRmKCIlZCAiLCBncmlkW2ldW2pdKTsKICAgICAgICBwcmludGYoIlxuIik7CiAgICB9Cgljb3V0IDw8ICJudW1iZXIgb2YgaXRlcmF0aW9ucyA6ICIgPDwgaXRlcmF0aW9ucyA8PCBlbmRsOwp9CiAKaW50IG1haW4oKQp7CiAgICBpbnQgdCwgaSwgajsKICAgIHNjYW5mKCIlZCIsICZ0KTsKICAgIHdoaWxlKHQtLSkKICAgIHsKICAgICAgICBxdWV1ZSA8cG9pbnQ+IGJmczsKIAogICAgICAgIC8vIHRha2luZyBpbnB1dAogICAgICAgIHNjYW5mKCIlZCAlZCIsICZuLCAmbSk7CiAgICAgICAgZm9yKGk9MDsgaTxuOyBpKyspCiAgICAgICAgICAgIHNjYW5mKCIlcyIsIGJvYXJkW2ldKTsKIAoJCS8vIHB1dHRpbmcgdGhlIHZhbHVlIGZvciBlYWNoIHBvaW50IHRvIGJlIC0xCiAgICAgICAgZm9yKGk9MDsgaTxuOyBpKyspCiAgICAgICAgICAgIGZvcihqPTA7IGo8bTsgaisrKQogICAgICAgICAgICBncmlkW2ldW2pdID0gLTE7CiAKICAgICAgICBmb3IoaT0wOyBpPG47IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGZvcihqPTA7IGo8bTsgaisrKQogICAgICAgICAgICB7CiAgICAgICAgICAgIAkvLyBpZiB0aGUgcG9pbnQgaXMgd2hpdGUsIHB1dHRpbmcgaXRzIHZhbHVlIHRvIGJlIDEsIGFuZCBwdXNoaW5nIGl0IG9udG8gdGhlIHF1ZXVlCiAgICAgICAgICAgICAgICBpZihib2FyZFtpXVtqXT09JzEnKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGdyaWRbaV1bal0gPSAwOwogICAgICAgICAgICAgICAgICAgIGJmcy5wdXNoKHBvaW50KGksaiwwKSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CgkJaXRlcmF0aW9ucz0wOwogICAgICAgIEJGUyhiZnMpOwogICAgfQogICAgcmV0dXJuIDA7Cn0KIAo=