H1

#include <iostream>
#include <map>
#include <queue>
using namespace std;
#define SIZE 3
bool isPrime[18]={false,false,true,true,false,true,false,true,false,false,false,true,false,true,false,false,false,true};

class TrieNode{
    private:
    static const int ALPHABETSIZE=9;
    public:
    int val;
    TrieNode *edges[ALPHABETSIZE];
    TrieNode(){val=-1; for(int i=0;i<ALPHABETSIZE;i++) edges[i]=NULL;}
};

class Trie{
    private:
    TrieNode *root;
    public:
    void insert(string s,int val);
    TrieNode *find(string s);
    Trie(){root=new TrieNode();}
};

void Trie::insert(string s,int val){
    TrieNode *tmp=root;
    for(int i=0;s[i];i++){
        if(!tmp->edges[s[i]-'1']){
            TrieNode *newNode=new TrieNode();
            tmp->edges[s[i]-'1']=newNode;
        }
        tmp=tmp->edges[s[i]-'1'];
    }
    tmp->val=val;
}

TrieNode *Trie::find(string s){
    TrieNode *tmp=root;
    for(int i=0;s[i];i++){
        if(!tmp->edges[s[i]-'1']) return NULL;
        tmp=tmp->edges[s[i]-'1'];
    }
    return tmp;
}

Trie *T=new Trie();

class Puzzle{
    public:
    int moves;
    int **matrix;
    Puzzle(int **s){
        moves=0;
        matrix=new int*[SIZE];
        for(int i=0;i<SIZE;i++) matrix[i]=new int[SIZE];
        for(int i=0;i<SIZE;i++) for(int j=0;j<SIZE;j++) matrix[i][j]=s[i][j];
    }
    Puzzle(){
        moves=0;
        matrix=new int*[SIZE];
        for(int i=0;i<SIZE;i++) matrix[i]=new int[SIZE];
    }
};
queue<Puzzle *> Q;

string getMapping(int **s){
    string str="";
    for(int i=0;i<SIZE;i++) for(int j=0;j<SIZE;j++)  str+='0'+s[i][j];
    return str;
}

bool isGoal(int **s){
    for(int i=0;i<SIZE;i++) for(int j=0;j<SIZE;j++) if(s[i][j]!=(i*SIZE+j+1)) return false;
    return true;
}

void print(Puzzle *p){
    cout<<p->moves<<endl;
    for(int i=0;i<SIZE;i++){ for(int j=0;j<SIZE;j++) cout<<p->matrix[i][j]<<'\t'; cout<<endl;}
    cout<<endl;
}

void solve(){
    while(!Q.empty()){
        //cout<<M.size()<<endl;
        Puzzle *src=Q.front();
        //print(src);
        Q.pop();
        for(int i=0;i<SIZE;i++)
            for(int j=0;j<SIZE;j++){
                if(i-1>=0 && isPrime[src->matrix[i-1][j]+src->matrix[i][j]]){
                    Puzzle *tmp=new Puzzle(src->matrix);
                    swap(tmp->matrix[i-1][j],tmp->matrix[i][j]);
                    tmp->moves=src->moves+1;
                    //if(isGoal(tmp->matrix)){cout<<tmp->moves<<endl; return;}
                    string img=getMapping(tmp->matrix);
                    TrieNode *t=T->find(img);
                    if(!t){T->insert(img,tmp->moves); Q.push(tmp);}
                }
                if(i+1<SIZE && isPrime[src->matrix[i+1][j]+src->matrix[i][j]]){
                    Puzzle *tmp=new Puzzle(src->matrix);
                    swap(tmp->matrix[i+1][j],tmp->matrix[i][j]);
                    tmp->moves=src->moves+1;
                    //if(isGoal(tmp->matrix)){cout<<tmp->moves<<endl; return;}
                    string img=getMapping(tmp->matrix);
                    TrieNode *t=T->find(img);
                    if(!t){T->insert(img,tmp->moves); Q.push(tmp);}
                }
                if(j-1>=0 && isPrime[src->matrix[i][j-1]+src->matrix[i][j]]){
                    Puzzle *tmp=new Puzzle(src->matrix);
                    swap(tmp->matrix[i][j-1],tmp->matrix[i][j]);
                    tmp->moves=src->moves+1;
                    //if(isGoal(tmp->matrix)){cout<<tmp->moves<<endl; return;}
                    string img=getMapping(tmp->matrix);
                    TrieNode *t=T->find(img);
                    if(!t){T->insert(img,tmp->moves); Q.push(tmp);}
                }
                if(j+1<SIZE && isPrime[src->matrix[i][j+1]+src->matrix[i][j]]){
                    Puzzle *tmp=new Puzzle(src->matrix);
                    swap(tmp->matrix[i][j+1],tmp->matrix[i][j]);
                    tmp->moves=src->moves+1;
                    //if(isGoal(tmp->matrix)){cout<<tmp->moves<<endl; return;}
                    string img=getMapping(tmp->matrix);
                    TrieNode *t=T->find(img);
                    if(!t){T->insert(img,tmp->moves); Q.push(tmp);}
                }
            }

    delete src;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    Puzzle *src=new Puzzle();
    for(int i=0;i<SIZE;i++) for(int j=0;j<SIZE;j++) src->matrix[i][j]=i*3+j+1;
    Q.push(src);
    T->insert(getMapping(src->matrix),src->moves);
    solve();
    int tests;
    cin>>tests;
    while(tests--){
        Puzzle *tmp=new Puzzle();
        for(int i=0;i<SIZE;i++) for(int j=0;j<SIZE;j++) cin>>tmp->matrix[i][j];
        string str=getMapping(tmp->matrix);
        TrieNode *t=T->find(str);
        if(t!=NULL) cout<<t->val<<endl;
        else{cout<<"-1"<<endl;}
    }
}