#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <list>


typedef char puzzle_t[3][3];

puzzle_t _puzzle_start = { {1, 2, 3},
			   {4, 5, 6},
			   {7, 8, 0} 
			};
puzzle_t _puzzle_stop =	{  {1, 2, 3},
			   {4, 0, 5},
			   {6, 7, 8}
			};
struct	context_t {
	std::list<puzzle_t*> abort_states;
	std::list<std::string> solution;
	int max_depth;
};


std::ostream& operator<<(std::ostream &s, const puzzle_t &p)
{
	for (int y=0; y<3; ++y)	{
		for (int x=0; x<3; ++x)	{
			s << (int)p[y][x] << " ";
		}
		s << std::endl;
	}
	return s;
}

bool solver_rec(puzzle_t& start, const puzzle_t& stop, int y0, int x0, int depth, context_t &ctx)
{
	// enough CPU cycles wasted
	if (depth >= ctx.max_depth) return false;

	// is the actual start a abort state?
	for (std::list<puzzle_t*>::iterator it = ctx.abort_states.begin(); it != ctx.abort_states.end(); ++it)	{
		bool abort = true;
		for (int y=0; y<3; ++y)	{
			for (int x=0; x<3; ++x)	{
				if (start[y][x] != (**it)[y][x]) abort=false;
			}
		}
		// this state will be checked by on of the parents, anyhow
		if (abort)	{
			return false;
		}
	}
	
	// are we done?
	bool done = true;
	for (int yy=0; yy<3; ++yy)	{
		for (int xx=0; xx<3; ++xx)	{
			if (start[yy][xx] != stop[yy][xx]) done= false;
		}
	}
	if (done) return true;

	// add this state to the list of abort states
	// it safe to push_front an stack objectpointer 
	// as we remove it again before stack is unwinded
	// or never ever touch it again
	puzzle_t p;
	memcpy(p, start, sizeof(p));
	ctx.abort_states.push_front(&p);

	for (int yy=0; yy<3; ++yy)	{
		for (int xx=0; xx<3; ++xx)	{
			// if the move is possible, take it
			if (((yy+1 == y0) || (yy-1 == y0)) && (xx == x0))	{
				std::swap(start[yy][xx], start[y0][xx]);
				if (solver_rec(start, stop, yy, x0, depth+1, ctx))	{
					std::stringstream s;
					s << depth << ". tile  " << yy << "/" << x0;
					ctx.solution.push_back(s.str());
					return true;
				}
				std::swap(start[yy][xx], start[y0][xx]);
			}
			if (((xx+1 == x0) || (xx-1 == x0)) && (yy == y0))	{
				std::swap(start[yy][x0], start[yy][xx]);
				if (solver_rec(start, stop, y0, xx, depth+1, ctx))	{
					std::stringstream s;
					s << depth << ". tile " << y0 << "/" << xx;
					ctx.solution.push_back(s.str());
					return true;
				}
				std::swap(start[yy][x0], start[yy][xx]);
			}
		}
	}
	// remove the abort state
	ctx.abort_states.pop_front();
	return false;
};

bool solver(puzzle_t& start, const puzzle_t& stop, int max_depth)	
{
	context_t ctx;
	
	// search for the 0 element
	int y0=-1, x0=-1;
	for (int y=0; y<3; ++y)	{
		for (int x=0; x<3; ++x)	{
			if (start[y][x] == 0) {
				y0 = y;
				x0 = x;
				break;
			}
		}
	}
	assert(y0 != -1);
	assert(x0 != -1);
	// breath first search, assures that a shortest solution is found
	for (ctx.max_depth=0; ctx.max_depth<max_depth; ++(ctx.max_depth))	{
		if (solver_rec(start, stop, y0, x0, 1, ctx))	{
			std::cout << "---SOLUTION---" << std::endl;
			for (std::list<std::string>::reverse_iterator it = ctx.solution.rbegin(); it != ctx.solution.rend(); ++it)	{
				std::cout << *it << std::endl;
			}
			return true;
		}
	}
	return false;
}

int main(int argc, char**argv)	
{
	// 3 argument == max_depth
	if (!solver(_puzzle_start, _puzzle_stop, 20))	{
		std::cout << "--- NO SOLUTION ---" << std::endl;
	}
	return 0;
}

#include
#include
#include
#include
#include

#define TRUE 1
#define FALSE 0

unsigned int a,b,c,d,e,f,g,h;
void main(void)
{
 unsigned char chk_crash(unsigned char,unsigned char,unsigned char);
 void draw_puzzle(void);
 clrscr();
 for (a=1;a<=8;a++);
  for (b=1;b<=8;b++);
   if (chk_crash(a,b,1))
     for (c=1;c<=8;c++)
      if ((chk_crash(c,b,1)) && (chk_crash(c,a,2)))
       for (d=1;d<=8;d++)
    if ((chk_crash(d,c,1)) && (chk_crash(d,b,2)) && (chk_crash(d,a,3)))
     for(e=1;e<=8;e++)
      if  ((chk_crash(e,d,1)) && (chk_crash(e,c,2)) && (chk_crash(e,b,3)) && (chk_crash(e,a,4)))
       for (f=1;f<=8;f++)
        if ((chk_crash(f,e,1)) && (chk_crash(f,d,2)) && (chk_crash(f,c,3)) && (chk_crash(f,b,4)) && (chk_crash(f,a,5)))
         for (g=1;g<=8;g++)
          if ((chk_crash(g,f,1)) && (chk_crash(g,e,2)) && (chk_crash(g,d,3)) && (chk_crash(g,c,4)) && (chk_crash(g,b,5)) && (chk_crash(g,a,6)))
           for (h=1;h<=8;h++)
        if ((chk_crash(h,g,1)) && (chk_crash(h,f,2)) && (chk_crash(h,e,3)) && (chk_crash(h,d,4)) && (chk_crash(h,c,5)) && (chk_crash(h,b,6)) && (chk_crash(h,a,7)))
        {
        draw_puzzle();
        getch();
        }
          getch();
 }
 unsigned char chk_crash(unsigned char i,unsigned char j,unsigned char d)
  {
   if ((i==j) || (abs(i-j)==d))
    return(FALSE);
   else
    return(TRUE);
  }
  void draw_puzzle(void)
  {
   unsigned char a1,b1,a2,b2,i,v;
   clrscr();
   for (a1=1;a1<=16;a1++)
    for (b1=18;b<=65;b1++)
     {
      gotoxy(b1,a1+d);
      a2=(a1-1)/2+1;
      b2=(b1-18)/6+1;
      if (((a2+b2)%2)==0)
       textcolor(11);
      else
       textcolor(1);
      cprintf("A\0");
      for (i=0;i<8;i++)
       {
    switch(i)
     {
      case 0:{v=a;break;}
      case 1:{v=b;break;}
      case 2:{v=c;break;}
      case 3:{v=d;break;}
      case 4:{v=e;break;}
      case 5:{v=f;break;}
      case 6:{v=g;break;}
      case 7:{v=h;break;}
     }
       gotoxy(15+6*v,5+i*2);
       cprintf("*\0");
       }
}
}

#include <iostream>
#include <fstream>
#include <string>
#include <ctime>
#include <map>
#include <queue>
using namespace std;
map <string , int> m;
queue < string > qs;
queue < int > qc,qd;
//struct state{
//    string s;
//    int c,d;
//};
//queue <state> q;
void puzzle(int cur,string s){
    if (m.find(s)==m.end()){
        m[s]=qd.front();
        if (cur-1>=0 && cur-1<=8 && cur!=6 && cur!=3){
            string temp=s;
            {char t=temp[cur]; temp[cur]=temp[cur-1]; temp[cur-1]=t; }
            qc.push(cur-1);
            qd.push(m[s]+1);
            qs.push(temp);
        }
        if (cur+1>=0 && cur+1<=8 && cur!=2 && cur!=5){
            string temp=s;
            {char t=temp[cur]; temp[cur]=temp[cur+1]; temp[cur+1]=t; }
            qc.push(cur+1);
            qd.push(m[s]+1);
            qs.push(temp);
        }
        if (cur-3>=0 && cur-3<=8){
            string temp=s;
            {char t=temp[cur]; temp[cur]=temp[cur-3]; temp[cur-3]=t; }
            qc.push(cur-3);
            qs.push(temp);
            qd.push(m[s]+1);
        }
        if (cur+3>=0 && cur+3<=8){
            string temp=s;
            {char t=temp[cur]; temp[cur]=temp[cur+3]; temp[cur+3]=t; }
            qc.push(cur+3);
            qs.push(temp);
            qd.push(m[s]+1);
        }
    }
    qs.pop();
    qc.pop();
    qd.pop();
}
int main () {
    clock_t cl=clock();
    ifstream in ("8puzzle.in");
    qs.push("123456780");
    qc.push(8);
    qd.push(0);
    while (!qs.empty())
        puzzle(qc.front(),qs.front());
    int t;
    for (in >> t;t>0;--t){
        string s,temp;
        for (int i=0;i<3;++i)
            for (int j=0;j<3;++j){
                in >> temp;
                if (temp=="-1")
                    temp="0";
                s+=temp;
            }
            if (m.find(s)==m.end())
                cout << "Impossible" << endl;
            else
                cout << m[s] << endl;
    }
    cout << "time: " << (clock()-cl) * 0.001 << endl;
    return 0;
}