#include<string>
#include<cstdio>
#include<vector>
#include<map>
#include<iostream>
using namespace std;
int ilenajpierw=15;	
int ilepozniej=11;
int gdzie(int liczba)
{
	int i;
	int x;
	for(i=8;i>=1;i--) { x=liczba%10; liczba/=10; if(x==0) return i; }
	return -1;
}
int ruch(int liczba,int a, int b)
{
	string s=""+liczba;
	int l=0;
	char temp;	
	temp=s[a];
	s[a]=str[b];
	s[b]=temp;
	for(i=8;i<=0;i--)
	{
	l*=10;
	l+=s[i];
	}
	return l;
}

int main()
{
	int i,j,k,l,m,n,o;
	int ilosc[9]={2,3,2,3,4,3,2,3,2};
	int dostepne[9][4]={{1,3,0,0},{0,2,4,0},{1,5,0,0},{0,4,6,0},{1,3,5,7},{2,4,8,0},{3,7,0,0},{4,6,8,0},{5,7,0,0}};
	
	map<int, int> gry;
	map<int, int>::iterator it;
	int pocz=876543210;
	int pocz1=876540213;
	int pocz2=876543201;
	gry[pocz]=0;
	gry[pocz1]=1;
	gry[pocz2]=1;
	gry[1]=-1;
	gry[876543211]=-1;

	vector<int>::iterator iter;
	vector<int> aktualne;
	vector<int> popszednie;
	cur.push_back(876540213);
	cur.push_back(876543201);
	
	int temp1,temp2;
	

	for(i=2;i<=ilenajpierw;i++)
	{
		popszednie.clear();
		popszednie=aktualne;
		aktualne.clear();
		for(iter=popszednie.begin();iter!=popszednie.end();iter++)
		{
			temp1=(*iter);
			for(k=0;k<=ile[gdzie(temp1)]-1;k++)
			{
				temp2=ruch(temp1,gdzie(temp1),poz[gdzie(temp1)][k]);
				it=gry.find(temp2);
				if(it==gry.end())
				{
					gry[temp2]=i;
					aktualne.push_back(temp2);
				}
			}
		}
	}
	
	int n,z;
	int a,b;
	cin >> n;
	int wej[n];
	bool prawda=false;
	for(z=0;z<n;z++)
	{
		a=0;
		cin >> b;
		a*=1000;
		a+=b;
		cin >> b;
		a*=1000;
		a+=b;
		cin >> b;
		a*=1000;
		a+=b;
		wej[z]=a;
		it=gry.find(a);
		if(it==gry.end()) prawda=true; 
	}

if(prawda==true)
{

for(i=ilenajpierw+1;i<=ilepozniej+ilenajpierw;i++)
	{
		popszednie.clear();
		popszednie=aktualne;
		aktualne.clear();
		for(iter=popszednie.begin();iter!=popszednie.end();iter++)
		{
			temp1=(*iter);
			for(k=0;k<=ile[gdzie(temp1)]-1;k++)
			{
				temp2=ruch(temp1,gdzie(temp1),poz[gdzie(temp1)][k]);
				it=gry.find(temp2);
				if(it==gry.end())
				{
					gry[temp2]=i;
					aktualne.push_back(temp2);
				}
			}
		}
	}
}

for(z=0;z<n;z++)
	{
	it=gry.find(wej[z]);
	if(it!=gry.end()) cout << (*it).second << "
";
	else cout << "-1
";
	}



	return 0;
}