Untitled

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

public class CleaningRobot {
	static int n, m;
	static int a[][];
	static int dx[] = { 0, 0, 1, -1 };
	static int dy[] = { 1, -1, 0, 0 };
	static int Qx[];
	static int Qy[];
	static int visit[][], visitVetBan[];
	static int d[][];
	static int xRobot, yRobot;

	static int cbiData[][];
	static int vetBanX[];
	static int vetBanY[];
	static int VetBan;
	static int ans;

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("RoBot"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		Scanner sc = new Scanner(System.in);
		int numTest = sc.nextInt();
		for (int tc = 1; tc <= numTest; tc++) {
			n = sc.nextInt();
			m = sc.nextInt();

			a = new int[n + 2][m + 2];
			VetBan = 0;
			vetBanX = new int[11];
			vetBanY = new int[11];
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= m; j++) {
					a[i][j] = sc.nextInt();
					if (a[i][j] == 3) {
						// xRobot = i;
						// yRobot = j;
						vetBanX[0] = i; // luu robot
						vetBanY[0] = j;
					}
					if (a[i][j] == 1) {
						VetBan++;
						vetBanX[VetBan] = i;
						vetBanY[VetBan] = j;
					}

				}
			}

			cbiData = new int[100][100];
			chuanBiDuLieu();

			boolean checkDonSachPhong = true;
			for (int i = 0; i <= VetBan; i++) {  //
				int sumDong = 0;
				for (int j = 0; j <= VetBan; j++) {
					sumDong += cbiData[i][j];

				}
				if (sumDong == 0)
				{
					checkDonSachPhong = false;
					break;
				}
			}
			System.out.println("Case #" + tc);

			if (!checkDonSachPhong)
				System.out.println("-1");
			else {
				ans = 1000000000;
				visitVetBan = new int[11];
				backTrack(0, 0, 0);
				System.out.println(ans);
			}
		}
	}

	public static void chuanBiDuLieu() {
		for (int i = 0; i < VetBan; i++) {
			for (int j = i + 1; j <= VetBan; j++) {
				int data = BFS(vetBanX[i], vetBanY[i], vetBanX[j], vetBanY[j]);
				cbiData[i][j] = data;
				cbiData[j][i] = data;
			}
		}
//		for (int i = 0; i <= VetBan; i++) {
//			for (int j = 0; j <= VetBan; j++) {
//				System.out.print(cbiData[i][j] + " ");
//			}
//			System.out.println();
//		}
	}

	public static void backTrack(int vetBanThux, int sum, int numVetBan) {
		if (numVetBan == VetBan) {
			ans = Math.min(ans, sum);
			return;
		}

		for (int i = 1; i <= VetBan; i++) { // tung vi tri trong hang

			if (visitVetBan[i] == 0) {
				visitVetBan[i] = 1;
				backTrack(i, sum + cbiData[vetBanThux][i], numVetBan + 1);
				visitVetBan[i] = 0;
			}
		}

	}

	public static int BFS(int x, int y, int vetBanxX, int vetBanxY) {
		Qx = new int[n * m];
		Qy = new int[n * m];
		visit = new int[n + 2][m + 2];
		d = new int[n + 2][m + 2];

		int front = 0;
		int rear = 0;

		Qx[rear] = x;
		Qy[rear] = y;
		rear++;
		visit[x][y] = 1;
		while (front != rear) {
			int tmpx = Qx[front];
			int tmpy = Qy[front];
			front++;

			for (int i = 0; i < 4; i++) {
				int xx = tmpx + dx[i];
				int yy = tmpy + dy[i];

				if (xx >= 1 && xx <= n && yy >= 1 && yy <= m
						&& visit[xx][yy] == 0) {

					if (a[xx][yy] != 2) {
						d[xx][yy] = d[tmpx][tmpy] + 1;
						visit[xx][yy] = 1;
						Qx[rear] = xx;
						Qy[rear] = yy;
						rear++;
					}

					if (xx == vetBanxX && yy == vetBanxY) {
						d[xx][yy] = d[tmpx][tmpy] + 1;
						return d[xx][yy];
					}
				}
			}
		}
//		for (int i = 1; i <= n; i++) {
//			for (int j = 1; j <= m; j++) {
//				System.out.print(d[i][j] + "  ");
//			}
//			System.out.println();
//		}
//
//		System.out.println();
//		System.out.println();
		return 0;

	}
}