Untitled

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

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

	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();
			B = new int[n][m];
			M = new int[50][2];
			count = 1;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					B[i][j] = sc.nextInt();
					if (B[i][j] == 1) {
						M[count][0] = i;
						M[count][1] = j;
						count++;
					}
					if (B[i][j] == 3) {
						M[0][0] = i;
						M[0][1] = j;
					}

				}
			}

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

			for (int i = 0; i < count; i++) {
				findDistance(i);
			}
			
			min = 1000;
			sum=0;
			play(0, 1);
			System.out.println("Case #"+t);
			System.out.println(min);
		}
		sc.close();
	}

	private static void play(int idx, int k) {
		// TODO Auto-generated method stub
		if(count>=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 = M[i][0];
				int y = M[i][1];
				sum+= dist[idx][x][y];
				play(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 = M[idx][0];
		int y = M[idx][1];
		queue.push(x);
		queue.push(y);

		while (!queue.empty()) {
			x = queue.pop();
			y = queue.pop();
			for (int i = 0; i < 8; 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) {
					dist[idx][nx][ny] = dist[idx][x][y] +1;
					queue.push(nx);
					queue.push(ny);
				}
			}

		}
	}

}

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

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

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

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

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

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