Untitled

#include<iostream>
using namespace std;
#define INF 1000000007
int q_x[100000];
int q_y[100000];
int top=-1;
int bot=-1;
void push(int i,int j)
{
	bot++;
	q_x[bot]=i;
	q_y[bot]=j;
}
void pop()
{
	top++;
}
bool is_emty()
{
	return top==bot;
}

int n,m;
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int a[101][101];
int vis[101][101];
int vis1[101];
int d[101][101];
int arr[101][101];
pair<int,int> vetban[100];
int cnt=1;
int ans;

void BFS(int i,int j)
{
	push(i,j);
	d[i][j]=0;
	vis[i][j]=1;
	while(!is_emty())
	{
		int f1 = q_x[top+1];
		int f2 = q_y[top+1];
		pop();
		for(int k=0;k<4;k++)
		{
			int i1 = f1+dx[k];
			int j1 = f2+dy[k];
			if(i1>=0&&i1<n && j1>=0&&j1<m && a[i1][j1]!=2)
			{
				if(!vis[i1][j1])
				{
					vis[i1][j1]=1;
					d[i1][j1]=d[f1][f2]+1;
					push(i1,j1);
				}

			}
		}
	}
}
void backtrack(int k,int v,int res)
{
	if(res>ans)
	{
		return;
	}
	if(k==cnt-1)
	{
		ans=min(ans,res);
		return;
	}
	for(int i=0;i<cnt;i++)
	{
		if(!vis1[i])
		{
			vis1[i]=1;
			backtrack(k+1,i,res+arr[v][i]);
			vis1[i]=0;
		}
	}
}
void reset()
{
	top=-1;
	bot=-1;
	for(int i=0;i<cnt;i++)
	{
		d[vetban[i].first][vetban[i].second]=0;
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			vis[i][j]=0;
		}
	}
}
int main()
{
	//freopen("input.txt","r",stdin);
	int t;
	cin>>t;
	for(int tc=1;tc<=t;tc++)
	{
		cnt=1;
		reset();
		cin>>n>>m;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				cin>>a[i][j];
				if(a[i][j]==3)
				{
					vetban[0].first=i;
					vetban[0].second=j;
				}
				else if(a[i][j]==1)
				{
					vetban[cnt].first=i;
					vetban[cnt].second=j;
					cnt++;
				}
			}
		}
		bool check=true;
		for(int i=0;i<cnt-1;i++)
		{
			BFS(vetban[i].first,vetban[i].second);
			for(int j=i+1;j<cnt;j++)
			{
				arr[i][j] = d[vetban[j].first][vetban[j].second];
				arr[j][i] = d[vetban[j].first][vetban[j].second];
				if( check&&i!=j && arr[i][j]==0)
					check=false;
			}
			reset();
		}
		if(check==false)
		{
			cout<<"Case #"<<tc<<endl<<-1<<endl;
		}
		else
		{
			ans=INF;
			vis1[0]=1;
			backtrack(0,0,0);
			cout<<"Case #"<<tc<<endl<<ans<<endl;
		}
	}
	return 0;
}