Untitled

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

public class Solution {
	static int n, m, min, count, sum;
	static int[] visit;
	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };
	static int[][][] dist;
	static int[][] room, D;
	static Queue queue = new Queue(100000);

	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("src/input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 1; t <= T; t++) {
			n = sc.nextInt();
			m = sc.nextInt();
			count = 1;
			D = new int[11][2];
			room = new int[n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					room[i][j] = sc.nextInt();
					if (room[i][j] == 3) {
						D[0][0] = i;
						D[0][1] = j;
					}
					if (room[i][j] == 1) {
						D[count][0] = i;
						D[count][1] = j;

						count++;
					}
				}
			}

			visit = new int[11];
			dist = new int[11][n][m];

			for (int i = 0; i < count; i++) {
				findDistance(i);
			}

			boolean check = false;
			int x = D[0][0];
			int y = D[0][1];

			for (int i = 0; i < 4 && !check; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
					if (dist[0][nx][ny] != 0) {
						check = true;
					}
				}
			}
			min = 10000;
			sum = 0;
			System.out.println("Case #" + t);
			if (!check) {
				min = -1;
			} else {
				if (count == 1) {
					min = 0;
				} else {
					clean(0, 1);
					if (min == 10000) {
						min = -1;
					}
				}
			}
			System.out.println(min);

		}
		sc.close();
	}

	private static void clean(int idx, int k) {
		// TODO Auto-generated method stub
		if (sum > min)
			return;
		if (k == count) {
			min = sum < min ? sum : min;
			return;
		}
		
		visit[idx] = 1;
		
		for(int i=1; i<count; i++) {
			if(visit[i]==0) {
				int x = D[i][0];
				int y = D[i][1];
				if(dist[idx][x][y]!=0) {
					sum+= dist[idx][x][y];
					clean(i, k+1);
					sum-= dist[idx][x][y];
				}
			}
		}
		
		visit[idx] = 0;
	}

	private static void findDistance(int idx) {
		// TODO Auto-generated method stub
		queue.reset();
		int x = D[idx][0];
		int y = D[idx][1];
		queue.push(x);
		queue.push(y);
		dist[idx][x][y] = 0;
		while (!queue.empty()) {
			x = queue.pop();
			y = queue.pop();

			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];

				if (nx >= 0 && ny >= 0 && nx < n && ny < m && dist[idx][nx][ny] == 0 && room[nx][ny] != 2) {
					dist[idx][nx][ny] = dist[idx][x][y]+1;
					queue.push(nx);
					queue.push(ny);
				}
			}

		}
	}

}

class Queue {
	static int f, r;
	static int[] arr;

	Queue(int c) {
		arr = new int[c];
		f = r = 0;
	}

	boolean empty() {
		return f == r;
	}

	void push(int data) {
		arr[r] = data;
		r++;
	}

	int pop() {
		int tmp = arr[f];
		f++;
		return tmp;
	}

	void reset() {
		f = r = 0;
	}
}