rt。感觉写的没什么问题。

码风可能较丑。

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int T[5][5]={{1,1,1,1,1},
			 	   {0,1,1,1,1},
			 	   {0,0,-1,1,1},
			 	   {0,0,0,0,1},
			 	   {0,0,0,0,0}};
const int dx[8]={-2,-2,-1,1,2,2,1,-1};
const int dy[8]={-1,1,2,2,1,-1,-2,-2};
struct Stat{
	int M[5][5];
	int x,y;
	int dep;	
};

void wr(Stat S){
	for(int i=0;i<5;i++){
		for(int j=0;j<5;j++)cout<<S.M[i][j]<<" ";
		cout<<endl;
	}
}
int F(Stat S){
	int cnt=0;
	for(int i=0;i<5;i++)for(int j=0;j<5;j++)cnt+=(T[i][j]!=S.M[i][j]);
	return cnt+1>>1;
}
bool chk(int x,int y){
	return (x>=0)&&(x<=4)&&(y>=0)&&(y<=4);
}
int ans=16;
void slv(){
	Stat f;f.dep=0;
	for(int i=0;i<5;i++){
		for(int j=0;j<5;j++){
			char t;
			cin>>t;
			if(t=='*')f.x=i,f.y=j,f.M[i][j]=-1;
			else f.M[i][j]=t-'0';
		}
	}
	queue<Stat> q;
	q.push(f);
	while(!q.empty()){
		Stat u=q.front();
		q.pop();
		if(u.dep>15)continue;
		if(F(u)==0){
			cout<<u.dep<<endl;
			return;
		}
		if(u.dep+F(u)>ans)continue;
		Stat N=u;
		N.dep++;
		int x=N.x;
		int y=N.y;
		for(int i=0;i<8;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(!chk(nx,ny))continue;
			swap(N.M[x][y],N.M[nx][ny]);
			N.x=nx,N.y=ny;
			q.push(N); 
		}
	}
	cout<<-1<<endl;
	return;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);
	int T;
	cin>>T;
	while(T--)slv();
}