代码：

#include <bits/stdc++.h>
using namespace std ;
int t , ans , goall[7][7]={
		0,0,0,0,0,0,0,
		0,1,1,1,1,1,0,
		0,2,1,1,1,1,0,
		0,2,2,3,1,1,0,
		0,2,2,2,2,1,0,
		0,2,2,2,2,2,0,
		0,0,0,0,0,0,0,
	};
struct Sta{
	int sta[7][7] ;
};
int xxx[11]={0,1,2,2,1,-1,-2,-2,-1};
int yyy[11]={0,2,1,-1,-2,-2,-1,1,2};
Sta goal,a,last;
inline int check( Sta aa ){
	int re = 0 ;
	for( int i = 1 ; i <= 5 ; ++i ){
		for( int j = 1 ; j <= 5 ; ++j ){
			if( aa.sta[i][j] != goal.sta[i][j] ){
				re ++ ;
			}
		}
	}
	return re+1>>1 ;
}
inline void qf(int now , Sta aa ){
	int f_x = check(aa);//检查与目标的差异 
	if( now > 15 ){
		return ;
	}
	if( now + f_x >= ans ){//如果已经不优 
		return ;
	}
	if( f_x == 0 ){//如果达成 
		ans = min( ans , now-1);
		return ;
	}
	int x , y ;
	for( int i = 1 ; i <= 5 ; ++i ){//寻找空格 
		for( int j = 1 ; j <= 5 ; ++j ){
			if( aa.sta[i][j] == 3 ){
				x = i ; 
				y = j ;
				break ;
			}
		}
	}
	for( int i = 1 ; i <= 8 ; ++i ){//移动 
		if( x + xxx[i] > 5 || x + xxx[i] < 1 ){
			continue ;
		} 
		if( y + yyy[i] > 5 || y + yyy[i] < 1 ){
			continue ;
		}
		Sta nxt = aa ;
		swap( nxt.sta[x][y] , nxt.sta[x+xxx[i]][y+yyy[i]] );
		if( last.sta != nxt.sta ){
			last = nxt ;
			qf( now+1 ,nxt );
		}
	} 
}
int main(){
	ios::sync_with_stdio(0);
	cin >> t;
    for( int i = 0 ; i < 7 ; ++i ){
    	for( int j = 0 ; j < 7 ; ++j ){
    		goal.sta[i][j] = goall[i][j] ;
		}
	}
	
	while( t -- ){
		ans = 16 ;
		char in ;
		for( int i = 1 ; i <= 5 ; ++i ){
			for( int j = 1 ; j <= 5 ; ++j){
				cin >> in ;
				if( in == '1' ){
					a.sta[i][j] = 1 ;
				}else{
					if( in == '0' ){
						a.sta [i][j] = 2 ;
					}else{
						if( in == '*'){
							a.sta[i][j] = 3 ;
						}
					}
				}
			}
		}
		qf(1,a);
		if( ans > 15 ){
			cout << -1 << endl;
		}else{
			cout << ans << endl;
		}
	} 
	return 0 ;
}