#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;
}