#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;
}