#include <bits/stdc++.h>
using namespace std;
long long myhash( const string & key )
{
long long hash = 0;
for(char c : key) {
c -= 'a';
hash = (hash<<4) | (long long)c;
}
return hash;
}
void put(long long& hash, int i, long long c) {
long long mask4 = (1LL<<4) - 1;
hash = (hash & (~(mask4<<(4*i)))) ^ (c<<(4*i));
}
void swap(long long& hash, int i, int j) {
long long icode = (hash >> (4*i)) & ((1LL<<4)-1);
long long jcode = (hash >> (4*j)) & ((1LL<<4)-1);
put(hash, i, jcode);
put(hash, j, icode);
}
// unordered_map<string, int, decltype(&myhash)> vis[] = {
// unordered_map<string, int, decltype(&myhash)>(0, myhash),
// unordered_map<string, int, decltype(&myhash)>(0, myhash)
// };
unordered_map<long long, int> vis[2];
int find(int id, long long xx, long long yy, int maxdepth) {
queue<pair<long long, int>> q;
q.push({xx, 0});
vis[id][xx] = 0;
int result = 123;
while(q.size()) {
auto cur = q.front(); q.pop();
//if(cur.second <= 2) cout << cur.first << " " << cur.second << endl;
if(id == 0 && cur.first == yy) {
return cur.second;
}
if(cur.second == 4) return result;
if(id == 1 && vis[1-id].count(cur.first)) {
return cur.second + vis[1-id][cur.first];
}
for(int i = 0; i < 10; i++) {
long long t = cur.first;
for(int len = 3; i+len/2 < 10 && i-len/2 >= 0; len += 2) {
swap(t, i-len/2, i+len/2);
if(!vis[id].count(t)) {
if(id == 1 && vis[1-id].count(t)) {
return cur.second + 1 + vis[1-id][t];
}
if(cur.second+1 < maxdepth) q.push({t, cur.second+1});
vis[id][t] = cur.second+1;
}
}
t = cur.first;
for(int len = 2; i+len/2 < 10 && i-len/2+1 >= 0; len += 2) {
swap(t, i-len/2+1, i+len/2);
if(!vis[id].count(t)) {
if(id == 1 && vis[1-id].count(t)) {
return cur.second + 1 + vis[1-id][t];
}
if(cur.second+1 < maxdepth) q.push({t, cur.second+1});
vis[id][t] = cur.second+1;
}
}
}
}
return result;
}
int main() {
ios_base::sync_with_stdio(0);
string s, e;
vis[0].max_load_factor(0.25);
vis[1].max_load_factor(0.25);
while(true) {
cin >> s >> e;
vis[0].clear();
vis[1].clear();
if (s == "*") break;
find(0, myhash(s), myhash(e), 4);
cout << min(9, find(1, myhash(e), myhash(s), 4)) << "\n";
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpsb25nIGxvbmcgbXloYXNoKCBjb25zdCBzdHJpbmcgJiBrZXkgKQp7Cglsb25nIGxvbmcgaGFzaCA9IDA7CiAgICBmb3IoY2hhciBjIDoga2V5KSB7CiAgICAJYyAtPSAnYSc7CiAgICAJaGFzaCA9IChoYXNoPDw0KSB8IChsb25nIGxvbmcpYzsKICAgIH0KICAgIHJldHVybiBoYXNoOwp9Cgp2b2lkIHB1dChsb25nIGxvbmcmIGhhc2gsIGludCBpLCBsb25nIGxvbmcgYykgewoJbG9uZyBsb25nIG1hc2s0ID0gKDFMTDw8NCkgLSAxOwoJaGFzaCA9IChoYXNoICYgKH4obWFzazQ8PCg0KmkpKSkpIF4gKGM8PCg0KmkpKTsKfQoKdm9pZCBzd2FwKGxvbmcgbG9uZyYgaGFzaCwgaW50IGksIGludCBqKSB7Cglsb25nIGxvbmcgaWNvZGUgPSAoaGFzaCA+PiAoNCppKSkgJiAoKDFMTDw8NCktMSk7Cglsb25nIGxvbmcgamNvZGUgPSAoaGFzaCA+PiAoNCpqKSkgJiAoKDFMTDw8NCktMSk7CglwdXQoaGFzaCwgaSwgamNvZGUpOwoJcHV0KGhhc2gsIGosIGljb2RlKTsKfQoKLy8gdW5vcmRlcmVkX21hcDxzdHJpbmcsIGludCwgZGVjbHR5cGUoJm15aGFzaCk+IHZpc1tdID0gewovLyAJdW5vcmRlcmVkX21hcDxzdHJpbmcsIGludCwgZGVjbHR5cGUoJm15aGFzaCk+KDAsIG15aGFzaCksCi8vIAl1bm9yZGVyZWRfbWFwPHN0cmluZywgaW50LCBkZWNsdHlwZSgmbXloYXNoKT4oMCwgbXloYXNoKQovLyB9OwoKdW5vcmRlcmVkX21hcDxsb25nIGxvbmcsIGludD4gdmlzWzJdOwoKCmludCBmaW5kKGludCBpZCwgbG9uZyBsb25nIHh4LCBsb25nIGxvbmcgeXksIGludCBtYXhkZXB0aCkgewoJcXVldWU8cGFpcjxsb25nIGxvbmcsIGludD4+IHE7CglxLnB1c2goe3h4LCAwfSk7Cgl2aXNbaWRdW3h4XSA9IDA7CglpbnQgcmVzdWx0ID0gMTIzOwoJd2hpbGUocS5zaXplKCkpIHsKCQlhdXRvIGN1ciA9IHEuZnJvbnQoKTsgcS5wb3AoKTsKCQkvL2lmKGN1ci5zZWNvbmQgPD0gMikgY291dCA8PCBjdXIuZmlyc3QgPDwgIiAiIDw8IGN1ci5zZWNvbmQgPDwgZW5kbDsKCQlpZihpZCA9PSAwICYmIGN1ci5maXJzdCA9PSB5eSkgewoJCQlyZXR1cm4gY3VyLnNlY29uZDsKCQl9CgkJaWYoY3VyLnNlY29uZCA9PSA0KSByZXR1cm4gcmVzdWx0OwoJCWlmKGlkID09IDEgJiYgdmlzWzEtaWRdLmNvdW50KGN1ci5maXJzdCkpIHsKCQkJcmV0dXJuIGN1ci5zZWNvbmQgKyB2aXNbMS1pZF1bY3VyLmZpcnN0XTsKCQl9CgkJZm9yKGludCBpID0gMDsgaSA8IDEwOyBpKyspIHsKCQkJbG9uZyBsb25nIHQgPSBjdXIuZmlyc3Q7CgkJCWZvcihpbnQgbGVuID0gMzsgaStsZW4vMiA8IDEwICYmIGktbGVuLzIgPj0gMDsgbGVuICs9IDIpIHsKCQkJCXN3YXAodCwgaS1sZW4vMiwgaStsZW4vMik7CgkJCQlpZighdmlzW2lkXS5jb3VudCh0KSkgewoJCQkJCWlmKGlkID09IDEgJiYgdmlzWzEtaWRdLmNvdW50KHQpKSB7CgkJCQkJCXJldHVybiBjdXIuc2Vjb25kICsgMSArIHZpc1sxLWlkXVt0XTsKCQkJCQl9CgkJCQkJaWYoY3VyLnNlY29uZCsxIDwgbWF4ZGVwdGgpIHEucHVzaCh7dCwgY3VyLnNlY29uZCsxfSk7CgkJCQkJdmlzW2lkXVt0XSA9IGN1ci5zZWNvbmQrMTsKCQkJCX0KCQkJfQoJCQl0ID0gY3VyLmZpcnN0OwoJCQlmb3IoaW50IGxlbiA9IDI7IGkrbGVuLzIgPCAxMCAmJiBpLWxlbi8yKzEgPj0gMDsgbGVuICs9IDIpIHsKCQkJCXN3YXAodCwgaS1sZW4vMisxLCBpK2xlbi8yKTsKCQkJCWlmKCF2aXNbaWRdLmNvdW50KHQpKSB7CgkJCQkJaWYoaWQgPT0gMSAmJiB2aXNbMS1pZF0uY291bnQodCkpIHsKCQkJCQkJcmV0dXJuIGN1ci5zZWNvbmQgKyAxICsgdmlzWzEtaWRdW3RdOwoJCQkJCX0KCQkJCQlpZihjdXIuc2Vjb25kKzEgPCBtYXhkZXB0aCkgcS5wdXNoKHt0LCBjdXIuc2Vjb25kKzF9KTsKCQkJCQl2aXNbaWRdW3RdID0gY3VyLnNlY29uZCsxOwoJCQkJfQoJCQl9CQoJCX0KCX0KCXJldHVybiByZXN1bHQ7Cn0KCmludCBtYWluKCkgewoJaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsKCXN0cmluZyBzLCBlOwoJdmlzWzBdLm1heF9sb2FkX2ZhY3RvcigwLjI1KTsKCXZpc1sxXS5tYXhfbG9hZF9mYWN0b3IoMC4yNSk7Cgl3aGlsZSh0cnVlKSB7CgkJY2luID4+IHMgPj4gZTsKCQl2aXNbMF0uY2xlYXIoKTsKCQl2aXNbMV0uY2xlYXIoKTsKCQlpZiAocyA9PSAiKiIpIGJyZWFrOwoJCWZpbmQoMCwgbXloYXNoKHMpLCBteWhhc2goZSksIDQpOwoJCWNvdXQgPDwgbWluKDksIGZpbmQoMSwgbXloYXNoKGUpLCBteWhhc2gocyksIDQpKSA8PCAiXG4iOwoJfQoJCglyZXR1cm4gMDsKfQ==