玄关，萌新求救

#include<bits/stdc++.h>
using namespace std;
const int maxn=5;
const int dx[]={0,1,1,-1,-1,2,2,-2,-2};
const int dy[]={0,2,-2,2,-2,1,-1,1,-1};
const int X[5][5]={
	{1,1,1,1,1},
	{0,1,1,1,1},
	{0,0,2,1,1},
	{0,0,0,0,1},
	{0,0,0,0,0}
};
struct node{
	int M[maxn][maxn];
	int x,y;//空地的坐标 
	int g;
	int h;
	int f;
	/*
	M[i][j]=1 黑色
	M[i][j]=0 白色
	M[i][j]=2 空地 
	*/
	bool operator<(const node&other) const{
		return f>other.f;
	}
	int toint(){
		int h=0;
		for(int i=0;i<5;i++){
			for(int j=0;j<5;j++){
				h=h*3+M[i][j];//采用三进制串存储 
			}
		}
		return h;
	}
	int G(){// 评估函数：计算当前状态到目标状态还需要多少步（预估，预估值<实际值） 
		int cnt=0;
		for(int i=0;i<5;i++){
			for(int j=0;j<5;j++){
				if(i!=x||j!=y){
					cnt+=bool(X[i][j]!=M[i][j]);
				}
			}
		}
		return cnt;
	}
	bool is_right()const{
		for(int i=0;i<5;i++){
			for(int j=0;j<5;j++){
				if(M[i][j]!=X[i][j]){
					return false;
				}
			}
		}
		return  true;
	}
};
char a[maxn][maxn];
int A_star(node st){
	priority_queue<node>q;
	map<int,int>vis;
	st.g=0;
	st.h=st.G();
	st.f=st.g+st.h;
	q.push(st);
	vis[st.toint()]=st.g;
	while(!q.empty()){
		node cur=q.top();
		//cout<<cur.x<<" "<<cur.y<<endl;
		q.pop();
		if(cur.g>15){
			continue;
		}
		if(cur.is_right()){
			return cur.g;
		}
		for(int i=0;i<8;i++){//枚举所有可以变换的位置 
			int nx=dx[i]+cur.x;
			int ny=dy[i]+cur.y;
			if(nx<0||nx>=5||ny<0||ny>=5){
				continue;
			}
			node nxt=cur;
			swap(nxt.M[cur.x][cur.y],nxt.M[nx][ny]);//与空地交换位置(将(nx,ny)的棋子移动到空地） 
			nxt.x=nx;
			nxt.y=ny;
			//评估函数计算+步数更新 
			nxt.g=cur.g+1;
			nxt.h=nxt.G();
			nxt.f=nxt.g+nxt.h;
			int state=nxt.toint();
			if(vis.count(state)==0||vis[state]>nxt.g){
				vis[state]=nxt.g;
				q.push(nxt);
			}
		}
	}
	return -1;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		node st;//初试状态 
		for(int i=0;i<5;i++){
			string line;
			cin>>line;
			for(int j=0;j<5;j++){
				if(line[j]=='0'){
					st.M[i][j]=0;
				}
				else if(line[j]=='1'){
					st.M[i][j]=1;
				}
				else{
					st.M[i][j]=2;
					st.x=i;
					st.y=j;
				}
			}
		}
		//cout<<st.x<<" "<<st.y<<endl;
		cout<<A_star(st)<<"\n";
	}
	return 0;
}