Untitled

// cleanning robot
package bla;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

class Queue{
	private int [] arr;
	private int size;
	private int front;
	private int rear;
	public Queue(int s){
		size = s;
		arr = new int [size];
		front = -1;
		rear = -1;
	}
	public boolean isEmpty(){
		if(front==rear){
			return true;
		}
		return false;
	}
	public boolean isFull(){
		if(rear == arr.length-1){
			return true;
		}
		return false;
	}
	public void push(int x){
		arr[++rear] = x;
	}
	public int pop(){
		front++;
		return arr[front];
	}
	public void reset(){
		front = rear = -1;
	}
}
public class Solution {
	static Queue Qx = new Queue(10000);
	static Queue Qy = new Queue(10000);
	static int [] dx = {0,-1,0,1};
	static int [] dy = {-1,0,1,0};
	static int [][] home = new int [10000][10000];
	static int [][] vetban = new int [12][2];
	static int [][] matrix = new int [10000][10000];
	static int [][] vis = new int [10000][10000];
	static int m,n;
	public static void reset(){
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				vis[i][j]=0;
			}
		}
	}
	public static int BFS(int startX ,int startY,int endX,int endY){
		int min = 0;
		Qx.push(startX);
		Qy.push(startY);
		vis[startX][startY] = 1;
		while(!Qx.isEmpty()){
			startX = Qx.pop();
			startY = Qy.pop();
			for (int i = 0; i < 4; i++) {
				int r = startX + dx[i];
				int c = startY + dy[i];
				if(r>=0 && c>=0 && r<m && c<n && vis[r][c] == 0) {
					if(r==endX && c==endY){
						min = vis[startX][startY];
						Qx.reset();
						Qy.reset();
						break;
					}else
					vis[r][c] = vis[startX][startY]+1;
					Qx.push(r);
					Qy.push(c);
				}
			}
		}
		return min;
	}
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			m = sc.nextInt();
			n = sc.nextInt();
			home = new int [m][n];
			int soVetBan = 1;
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					home[i][j] = sc.nextInt();
					if(home[i][j]==3){
						vetban[0][0] = i;
						vetban[0][1] = j;
					}else if (home[i][j]==1){
						vetban[soVetBan][0]=i;
						vetban[soVetBan][1]=j;
						soVetBan++;
					}
				}
			}
			
			matrix = new int [soVetBan][soVetBan];
			
			for (int i = 0; i < soVetBan; i++) {
				for (int j = 0; j < soVetBan; j++) {
					if(i==j){
						matrix[i][j]=0;
					}else{
						reset();
						Qx.reset();
						Qy.reset();
						matrix[i][j] = BFS(vetban[0][0],vetban[0][1],vetban[i+1][0],vetban[i+1][1]);
						matrix[j][i] = matrix[i][j];
					}
					
				}
			}
			for (int i = 0; i < soVetBan; i++) {
				for (int j = 0; j < soVetBan; j++) {
					System.out.print(matrix[i][j]+" ");
				}
				System.out.println();
			}
			System.out.println();
		}
	}
}

//2

5 7

0 0 0 0 0 0 0

0 3 0 0 0 1 0

0 0 0 0 0 0 0

0 1 0 0 0 1 0

0 0 0 0 0 0 0

5 15

0 0 0 0 2 0 2 0 0 0 0 1 2 0 1

0 0 0 1 0 2 0 2 2 0 1 2 0 0 0

2 1 0 2 0 1 0 2 0 0 0 0 0 0 0

0 0 0 1 0 2 0 0 1 2 0 0 2 0 0

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

//