折磨題
必須自己手暴 HASH，否則 STL 得太慢 然後一大堆轉移控制
//
// GGGGGGGGGGGGG CCCCCCCCCCCCC AAA
// GGG::::::::::::G CCC::::::::::::C A:::A
// GG:::::::::::::::G CC:::::::::::::::C A:::::A
// G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A
// G:::::G GGGGGG C:::::C CCCCCC A:::::::::A
//G:::::G C:::::C A:::::A:::::A
//G:::::G C:::::C A:::::A A:::::A
//G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A
//G:::::G G::::::::GC:::::C A:::::A A:::::A
//G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A
//G:::::G G::::GC:::::C A:::::::::::::::::::::A
// G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A
// G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A
// GG:::::::::::::::G CC:::::::::::::::C A:::::A A:::::A
// GGG::::::GGG:::G CCC::::::::::::C A:::::A A:::::A
// GGGGGG GGGG CCCCCCCCCCCCCAAAAAAA AAAAAAA
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <queue>
#include <cctype>
#include <utility>
#include <ctime>
using namespace std;
#ifdef DEBUG
#define debug(...) printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#define gettime() end\_time=clock();printf("now running time is %.7f\\n",(float)(end\_time - start\_time)/CLOCKS\_PER\_SEC);
#else
#define debug(...)
#define gettime()
#endif
typedef unsigned int uint;
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\\n")
#define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln()
#define De(x)printf(#x"%d\\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\
printf("%d ",dp\[htx\]\[hty\]);}Pln();}
#define M 55
#define PII pair<int,int\>
#define PB push\_back
#define oo INT\_MAX
#define Set\_oo 0x3f
#define FOR(it,c) for(\_\_typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
clock\_t start\_time=clock(), end\_time;
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
int tmp=min(x,y);
return min(tmp,z);
}
int max3(int x,int y,int z){
int tmp=max(x,y);
return max(tmp,z);
}
const int mod=1000003;
struct nodes{
char str\[10\];
bool minus\[10\];
int step;
}q\[mod\];
int head\[mod\],\_next\[mod\];
int isprime\[\] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1};
int mz\[10\]\[10\];
inline void inithash(){
Set(head,-1);
Set(\_next,-1);
}
inline int \_hash(int x){
int ans;
sscanf(q\[x\].str,"%d",&ans);
// debug("%d\\n",ans);
return ans%mod;
}
inline bool insert(int ins){
int hashcode=\_hash(ins);
int i,h=head\[hashcode\];
for(i=h;i!=-1;i=\_next\[i\]){
if(!strcmp(q\[i\].str,q\[ins\].str))return false;
}
if(i==-1){
\_next\[ins\]=h;
head\[hashcode\]=ins;
return true;
}
return false;
}
int x\[10\];
void buildgraph(){
Set(mz,0);
for(int i=0;i<8;i++){
for(int j=i+1;j<8;j++){
if(x\[i\]\*x\[j\]<0&&isprime\[abs(x\[i\])+abs(x\[j\])\]){
mz\[i\]\[j\]=mz\[j\]\[i\]=1;
debug("mz %d %d\\n",i,j);
}
}
}
}
bool dancer(nodes &now,int x,int y){
if(x+1==y)return false;
if(x-1==y){
swap(now.str\[x\],now.str\[y\]);
swap(now.minus\[x\],now.minus\[y\]);
}
else{
char tmp=now.str\[y\];
bool btmp=now.minus\[y\];
if(y>x){
for(int i=y;i>=x+2;i--){
now.str\[i\]=now.str\[i-1\];
now.minus\[i\]=now.minus\[i-1\];
}
now.str\[x+1\]=tmp;
now.minus\[x+1\]=btmp;
}else{
for(int i=y;i<x;i++){
now.str\[i\]=now.str\[i+1\];
now.minus\[i\]=now.minus\[i+1\];
}
now.str\[x\]=tmp;
now.minus\[x\]=btmp;
}
}
return true;
}
bool dancel(nodes &now,int x,int y){
if(x-1==y)return false;
if(x+1==y){
swap(now.str\[x\],now.str\[y\]);
swap(now.minus\[x\],now.minus\[y\]);
}
else{
char tmp=now.str\[y\];
bool btmp=now.minus\[y\];
if(y>x){
for(int i=y;i>=x+1;i--){
now.str\[i\]=now.str\[i-1\];
now.minus\[i\]=now.minus\[i-1\];
}
now.str\[x\]=tmp;
now.minus\[x\]=btmp;
}else{
for(int i=y;i<x-1;i++){
now.str\[i\]=now.str\[i+1\];
now.minus\[i\]=now.minus\[i+1\];
}
now.str\[x-1\]=tmp;
now.minus\[x-1\]=btmp;
}
}
return true;
}
bool isok(int x){
for(int i=1;i<8;i++){
if(q\[x\].str\[i\]!=q\[x\].str\[i-1\]+1)return false;
}
return true;
}
void bfs(){
inithash();
for(int i=0;i<8;i++)q\[0\].str\[i\]=abs(x\[i\])+'0';
for(int i=0;i<8;i++)q\[0\].minus\[i\]=(x\[i\]<0)?1:0;
q\[0\].str\[8\]='';
q\[0\].step=0;
insert(0);
int front=1,rear=0;
// debug("%s\\n",q\[0\].str);
int ans=-1;
while(front>rear){
nodes now=q\[rear\];
// debug("%s %d\\n",now.str,now.step);
if(isok(rear)){
ans=now.step;
break;
}
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
if(i==j||(now.minus\[i\]&&now.minus\[j\])||(!now.minus\[i\]&&!now.minus\[j\])||(!isprime\[(now.str\[i\]-'0')+(now.str\[j\]-'0')\]))continue;
nodes tmp=now;
// if(!mz\[i\]\[j\]||i==j)continue;
dancer(tmp,i,j);
q\[front\]=tmp;
if(insert(front)){
// debug("ch %d %d\\n %s\\n",i,j,q\[front\].str);
q\[front\].step=now.step+1;front++;
}
tmp=now;
dancel(tmp,i,j);
q\[front\]=tmp;
if(insert(front)){
// debug("ch1 %d %d\\n %s\\n",i,j,q\[front\].str);
q\[front\].step=now.step+1;front++;
}
}
}
rear++;
// if(rear>=50)break;
}
printf("%d\\n",ans);
}
int main() {
ios\_base::sync\_with\_stdio(0);
int ff=0;
while(~scanf("%d",&x\[0\])&&x\[0\]){
for(int i=1;i<8;i++)scanf("%d",&x\[i\]);
printf("Case %d: ",++ff);
bfs();
}
}