CodeChef submission 108738 (C) plaintext list. Status: WA, problem H1, contest OCT09. By avd122 (Aditya), 2009-10-11 12:44:30.
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<unistd.h>
#define ext(hash,i) ( ((hash)>>(((i)-1)*4)) & 15 )
#define MAX(a,b) ((a)>(b)?(a):(b))
#define INF 0x7FFFFFFF
#define TSIZE 362897
 
typedef struct _node{
long long hash;
int b;
int cnt;
struct _node *next;
}node;
 
 
node **table;
int i = 0;
int pri[] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1};
long long  orihash;
long long zero[] = {1,0x0FFFFFFFFFFFFFF0LL,
                      0x0FFFFFFFFFFFFF0FLL,
                      0x0FFFFFFFFFFFF0FFLL,
                      0x0FFFFFFFFFFF0FFFLL,
                      0x0FFFFFFFFFF0FFFFLL,
                      0x0FFFFFFFFF0FFFFFLL,
                      0x0FFFFFFFF0FFFFFFLL,
                      0x0FFFFFFF0FFFFFFFLL,
                      0x0FFFFFF0FFFFFFFFLL };
 
int find(long long hash) {
	node *tmpnext,*newnode;
	int place,flag=1;
	long long nhash,t1,t2;
//printf("%d: %llX\n",++i,hash);
	place = hash%TSIZE;	
	tmpnext=table[place];
	while(tmpnext!=NULL) {
		if(tmpnext->hash == hash) {
			flag  = 0;
			if(tmpnext->b)
				return tmpnext->cnt;
			break;
		}
		tmpnext = tmpnext->next;
	}
	if(flag) {
		newnode = (node*)malloc(sizeof(node));
		newnode->b = 0;
		newnode->hash = hash;
		newnode->next = table[place];
		table[place] = newnode;
	}	
 
	int mincnt = INF,cnt,nplace,i;
	for(i=1;i<=9;i++) {
	//	if( i == ext(hash,i) )
	//		continue;
		if(!(i==7 || i==8 || i==9) && pri[ext(hash,i)+ext(hash,i+3)]) {
			t1=ext(hash,i);
			t2=ext(hash,i+3);
			nhash = (hash & zero[i] & zero[i+3]) |  (t2<<((i-1)*4)) | (t1<<((i+3-1)*4));
			if(nhash == orihash){
				newnode->b = 1;
				newnode->cnt = 1;
				return 1;
			}
			nplace = nhash%TSIZE;
			tmpnext = table[nplace];
			flag=1;
			while(tmpnext!=NULL) {
				if(tmpnext->hash == nhash){
					flag=0;
					break;
				}
				tmpnext = tmpnext->next;
			}
			if(flag) {
				cnt=find(nhash);
				if(cnt > 0 && cnt<mincnt){
					mincnt = cnt;
				}
			}
		}
 
		if(!(i==1 || i==2 || i==3) && pri[ext(hash,i)+ext(hash,i-3)]) {
			t1=ext(hash,i);
			t2=ext(hash,i-3);
			nhash = (hash & zero[i] & zero[i-3]) |  (t2<<((i-1)*4)) | (t1<<((i-3-1)*4));
 
			if(nhash == orihash){
				newnode->b = 1;
				newnode->cnt = 1;
				return 1;
			}
			nplace = nhash%TSIZE;
			tmpnext = table[nplace];
			flag=1;
			while(tmpnext!=NULL) {
				if(tmpnext->hash == nhash){
					flag=0;
					break;
				}
				tmpnext = tmpnext->next;
			}
			if(flag) {
				cnt=find(nhash);
				if(cnt > 0 && cnt<mincnt){
					mincnt = cnt;
				}
			}
		}
 
		if(!(i==1 || i==4 || i==7) && pri[ext(hash,i)+ext(hash,i-1)]) {
			t1=ext(hash,i);
			t2=ext(hash,i-1);
			nhash = (hash & zero[i] & zero[i-1]) |  (t2<<((i-1)*4)) | (t1<<((i-1-1)*4));
 
			if(nhash == orihash){
				newnode->b = 1;
				newnode->cnt = 1;
				return 1;
			}
			nplace = nhash%TSIZE;
			tmpnext = table[nplace];
			flag=1;
			while(tmpnext!=NULL) {
				if(tmpnext->hash == nhash){
					flag=0;
					break;
				}
				tmpnext = tmpnext->next;
			}
			if(flag) {
				cnt=find(nhash);
				if(cnt > 0 && cnt<mincnt){
					mincnt = cnt;
				}
			}
		}
		if(!(i==3 || i==6 || i==9) && pri[ext(hash,i)+ext(hash,i+1)]) {
			t1=ext(hash,i);
			t2=ext(hash,i+1);
			nhash = (hash & zero[i] & zero[i+1]) |  (t2<<((i-1)*4)) | (t1<<((i+1-1)*4));
 
			if(nhash == orihash){
				newnode->b = 1;
				newnode->cnt = 1;
				return 1;
			}
			nplace = nhash%TSIZE;
			tmpnext = table[nplace];
			flag=1;
			while(tmpnext!=NULL) {
				if(tmpnext->hash == nhash){
					flag=0;
					break;
				}
				tmpnext = tmpnext->next;
			}
			if(flag) {
				cnt=find(nhash);
				if(cnt > 0 && cnt<mincnt){
					mincnt = cnt;
				}
			}
		}
	}
 
 
	newnode->b = 1;
	if(mincnt == INF)
		return (newnode->cnt = -1);
	else 
	        return	(newnode->cnt = mincnt+1);
}
 
 
int main() {
//freopen("in.txt","r",stdin);
table = (node**)malloc(sizeof(node*) *TSIZE);
memset(table,0,sizeof(node*)*TSIZE);
orihash=1|2<<4|3<<8|4<<12|5<<16|6<<20|7<<24|(long long)8<<28|(long long)9<<32;
//printf("%llX\n",orihash);
long long hash;
int tc,i,j,k,tmp;
scanf("%d",&tc);
for(i=0;i<tc;i++){
	hash=0;
	k=0;
	for(j=0;j<9;j++) {
	   scanf("%d",&tmp);
	   hash|=(long long)tmp<<k;
	   k+=4;
	}
	//printf("%llX\n",hash);
	if(hash==orihash)
		printf("0\n");
	else
		printf("%d\n",find(hash));
}	
return 0;
}