#include <iostream>
#include <bits/stdc++.h>
#define inf 1000000
using namespace std;
int curr_state[50],n;
int lim,nlim,result;
int dx[4][4] = {
{ -3, -1, +4, -4 },
{ +1, +3, +4, -4 },
{ +1, -1, +4, -4 },
{ +1, -1, +4, -4 }
};
int manhattan_distance(int p1,int p2);
int dh(int curr_point,int prev_point,int val) //delta
{
return manhattan_distance(curr_point,val)-manhattan_distance(prev_point,val);
}
int h1()
{
int h = 0;
for(int i=1;i<=n;++i)
h+=manhattan_distance(i,curr_state[i]);
return h;
}
int parents[50];
bool dfs(int depth,int cost ,int parent,int i)
{
parents[i] = parent;
if(depth+cost > lim)
{
nlim = min(nlim,depth+cost);
return false;
}
if(!cost){
result = depth;
return true;
}
int *d = dx[i % 4];
for (int j = 0; j < 4; j++)
{
int k = i + d[j];
if (k < 1 || k > n || k == parent) continue;
swap(curr_state[i],curr_state[k]);
int d = dh(k,i,curr_state[k]) + dh(i,k,curr_state[i]);
if(dfs(depth+1,cost+d,i,k))
return true;
swap(curr_state[i],curr_state[k]);
}
return false;
}
int IDA_Star(int kings_pos) {
lim = h1();
int h = h1();
while (true) {
nlim = inf;
if (dfs(0, h,-1,kings_pos))
return result;
if (nlim == inf)
return -1;
lim = nlim;
}
}
int main()
{
int p1,p2;
int set_no = 1;
while(cin>>n && n){
int kings_pos;
for(int i=1;i<=n;++i)
{
cin>>curr_state[i];
if(curr_state[i] == 1)
kings_pos = i;
}
cout<<"Set "<<set_no++<<":"<<endl;
cout<<IDA_Star(kings_pos)<<endl;
}
}
int manhattan_distance(int p1,int p2)
{
--p1;
--p2;
int res = abs(p1%4 - p2%4) + abs(p1/4 - p2/4);
if((p1%4 == 0 && p2%4 == 3)||(p2%4 == 0 && p1%4 == 3))
res-=2;
return res;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBpbmYgMTAwMDAwMAp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgY3Vycl9zdGF0ZVs1MF0sbjsKaW50IGxpbSxubGltLHJlc3VsdDsKaW50IGR4WzRdWzRdID0gewp7IC0zLCAtMSwgKzQsIC00IH0sCnsgKzEsICszLCArNCwgLTQgfSwKeyArMSwgLTEsICs0LCAtNCB9LAp7ICsxLCAtMSwgKzQsIC00IH0KICAgIH07CmludCBtYW5oYXR0YW5fZGlzdGFuY2UoaW50IHAxLGludCBwMik7CmludCBkaChpbnQgY3Vycl9wb2ludCxpbnQgcHJldl9wb2ludCxpbnQgdmFsKSAvL2RlbHRhCnsKICAgIHJldHVybiBtYW5oYXR0YW5fZGlzdGFuY2UoY3Vycl9wb2ludCx2YWwpLW1hbmhhdHRhbl9kaXN0YW5jZShwcmV2X3BvaW50LHZhbCk7Cn0KaW50IGgxKCkKewogICAgaW50IGggPSAwOwogICAgZm9yKGludCBpPTE7aTw9bjsrK2kpCiAgICAgICAgaCs9bWFuaGF0dGFuX2Rpc3RhbmNlKGksY3Vycl9zdGF0ZVtpXSk7CiAgICByZXR1cm4gaDsKfQppbnQgcGFyZW50c1s1MF07CmJvb2wgZGZzKGludCBkZXB0aCxpbnQgY29zdCAsaW50IHBhcmVudCxpbnQgaSkKewogICAgcGFyZW50c1tpXSA9IHBhcmVudDsKICAgIGlmKGRlcHRoK2Nvc3QgPiBsaW0pCiAgICB7CiAgICAgICAgbmxpbSA9IG1pbihubGltLGRlcHRoK2Nvc3QpOwogICAgICAgIHJldHVybiBmYWxzZTsKICAgIH0KICAgIGlmKCFjb3N0KXsKICAgICAgICByZXN1bHQgPSBkZXB0aDsKICAgICAgICByZXR1cm4gdHJ1ZTsKICAgIH0KICAgIGludCAqZCA9IGR4W2kgJSA0XTsKICAgIGZvciAoaW50IGogPSAwOyBqIDwgNDsgaisrKQogICAgewogICAgICAgIGludCBrID0gaSArIGRbal07CiAgICAgICAgaWYgKGsgPCAxIHx8IGsgPiBuIHx8IGsgPT0gcGFyZW50KSBjb250aW51ZTsKICAgICAgICBzd2FwKGN1cnJfc3RhdGVbaV0sY3Vycl9zdGF0ZVtrXSk7CiAgICAgICAgaW50IGQgPSBkaChrLGksY3Vycl9zdGF0ZVtrXSkgKyBkaChpLGssY3Vycl9zdGF0ZVtpXSk7CiAgICAgICAgaWYoZGZzKGRlcHRoKzEsY29zdCtkLGksaykpCiAgICAgICAgICAgIHJldHVybiB0cnVlOwogICAgICAgIHN3YXAoY3Vycl9zdGF0ZVtpXSxjdXJyX3N0YXRlW2tdKTsKICAgIH0KICAgIHJldHVybiBmYWxzZTsKfQoKCgoKaW50IElEQV9TdGFyKGludCBraW5nc19wb3MpIHsKICBsaW0gPSBoMSgpOwogIGludCBoID0gaDEoKTsKICB3aGlsZSAodHJ1ZSkgewogICAgbmxpbSA9IGluZjsKICAgIGlmIChkZnMoMCwgaCwtMSxraW5nc19wb3MpKQogICAgICByZXR1cm4gcmVzdWx0OwogICAgaWYgKG5saW0gPT0gaW5mKQogICAgICByZXR1cm4gLTE7CgogICAgbGltID0gbmxpbTsKICB9Cn0KCmludCBtYWluKCkKewoKICAgIGludCBwMSxwMjsKICAgIGludCBzZXRfbm8gPSAxOwogICAgd2hpbGUoY2luPj5uICYmIG4pewogICAgICAgIGludCBraW5nc19wb3M7CiAgICAgICAgZm9yKGludCBpPTE7aTw9bjsrK2kpCiAgICAgICAgewoKICAgICAgICAgICAgY2luPj5jdXJyX3N0YXRlW2ldOwogICAgICAgICAgICBpZihjdXJyX3N0YXRlW2ldID09IDEpCiAgICAgICAgICAgICAgICBraW5nc19wb3MgPSBpOwogICAgICAgIH0KICAgICAgICBjb3V0PDwiU2V0ICI8PHNldF9ubysrPDwiOiI8PGVuZGw7CiAgICAgICAgY291dDw8SURBX1N0YXIoa2luZ3NfcG9zKTw8ZW5kbDsKCiAgICB9CgoKfQppbnQgbWFuaGF0dGFuX2Rpc3RhbmNlKGludCBwMSxpbnQgcDIpCnsKIC0tcDE7CiAtLXAyOwppbnQgcmVzID0gYWJzKHAxJTQgLSBwMiU0KSArIGFicyhwMS80IC0gcDIvNCk7CiAgICBpZigocDElNCA9PSAwICYmIHAyJTQgPT0gMyl8fChwMiU0ID09IDAgJiYgcDElNCA9PSAzKSkKICAgIHJlcy09MjsKcmV0dXJuIHJlczsKfQoK