#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
#include<cmath>
#include<queue>
#include<cstdlib>
#pragma comment(linker,"/STACK:102400000,1024000")
using namespace std;
const long long inf=LLONG_MAX,total=462879;
const long long mo[25]={1,1,2,6,24,120,720,5040,40320,362880,3628800,
39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,
355687428096000,6402373705728000,121645100408832000,2432902008176640000};
inline const void read(long long &a)
{
char c=getchar();
while((c<'0'||c>'9')&&c!='*')c=getchar();
a=c-'0';
}
bool used[10];
long long present[10];
inline const long long cantor(long long graph[10])
{
long long ans=0;
memset(used,false,sizeof(used));
for(int i=1;i<=9;i++)
{
long long num=0,j;
for(j=1;j<=9;j++)if(!used[j]&&j<graph[i])num++;
ans+=mo[9-i]*num;
used[graph[i]]=true;
}
return ans;
}
inline const void uncantor(long long node)
{
long long m=node;
memset(used,false,sizeof(used));
for(long long i=9;i>=1;i--)
{
long long k=m/mo[i-1],num=0;
m%=mo[i-1];
long long j;
for(j=1;num<k;j++)if(!used[j])num++;
while(used[j])j++;
used[j]=true;
present[9-i+1]=j;
}
}
inline long long to_up(long long node,long long l)
{
long long now[10];
uncantor(node);
for(long long i=1;i<=9;i++)now[i]=present[i];
swap(now[l],now[l+6]);
swap(now[l],now[l+3]);
return cantor(now);
}
inline long long to_down(long long node,long long l)
{
long long now[10];
uncantor(node);
for(long long i=1;i<=9;i++)now[i]=present[i];
swap(now[l],now[l+6]);
swap(now[l+3],now[l+6]);
return cantor(now);
}
inline long long to_left(long long node,long long h)
{
long long now[10];
uncantor(node);
for(long long i=1;i<=9;i++)now[i]=present[i];
swap(now[(h-1)*3+1],now[(h-1)*3+3]);
swap(now[(h-1)*3+1],now[(h-1)*3+2]);
return cantor(now);
}
inline long long to_right(long long node,long long h)
{
long long now[10];
uncantor(node);
for(long long i=1;i<=9;i++)now[i]=present[i];
swap(now[(h-1)*3+1],now[(h-1)*3+3]);
swap(now[(h-1)*3+2],now[(h-1)*3+3]);
return cantor(now);
}
bool vis[total*9];
long long dis[total*9];
queue<long long> path;
void dijkstra()
{
long long x,node=path.front();
for(long long i=1;i<=3;i++)
{
x=to_up(node,i);
if(!vis[x])
{
dis[x]=dis[node]+1;
path.push(x);
vis[x]=true;
}
x=to_down(node,i);
if(!vis[x])
{
dis[x]=dis[node]+1;
path.push(x);
vis[x]=true;
}
x=to_left(node,i);
if(!vis[x])
{
dis[x]=dis[node]+1;
path.push(x);
vis[x]=true;
}
x=to_right(node,i);
if(!vis[x])
{
dis[x]=dis[node]+1;
path.push(x);
vis[x]=true;
}
}
path.pop();
if(!path.empty())dijkstra();
else return ;
}
long long answer;
inline const void try_ans(long long graph[10],long long d)
{
if(d==10)
{
answer=min(dis[cantor(graph)],answer);
return ;
}
if(!graph[d])
{
long long now[10];
for(long long i=1;i<=9;i++)now[i]=graph[i];
for(long long i=1;i<=9;i++)
{
now[d]=i;
try_ans(now,d+1);
}
return ;
}
else
{
try_ans(graph,d+1);
return ;
}
}
inline const void find_ans(long long graph[10],long long num)
{
answer=inf;
try_ans(graph,1);
if(answer==inf)printf("Case #%lld: No Solution!\n",num);
else printf("Case #%lld: %lld\n",num,answer);
}
long long t,k;
int main()
{
//freopen("测试数据.txt","r",stdin);
for(long long i=1;i<=total+1;i++)dis[i]=inf;
dis[0]=0;vis[0]=true;
memset(vis,false,sizeof(vis));
path.push(0);
dijkstra();
cin>>t;
for(long long i=1;i<=t;i++)
{
long long init[10],end[10];
for(long long j=1;j<=9;j++)
{
read(k);
init[k]=j;
}
for(long long j=1;j<=9;j++)
{
read(k);
if(k)end[j]=init[k];
}
find_ans(end,i);
}
return 0;
}